Sachverhalt: A. Am 9., mitgeteilt am 12. Juli 2012, erteilte die Baukommission der Gemeinde Arosa dem Gesuchsteller C._ die Bewilligung zum Neubau eines Mehrfamilienhauses auf Parzelle 2001 am Seehaldenweg in Arosa (Baubewilligung 2012 Nr. 26). Grundeigentümer der entsprechenden Parzelle ist E._. Die Bewilligung wurde für vier Zweitwohnungen erteilt und eine Lenkungsabgabe von gesamthaft Fr. 243'222.-- verfügt, gestützt auf das kommunale Gesetz über die Kontingentierung von Zweitwohnungen und die Erhebung einer Lenkungsabgabe vom 23. Oktober 2011 (im Folgenden: KontG/Arosa). Weiter wurde verfügt, dass die Baufreigabe nach der Einzahlung der Lenkungsabgabe ab dem 16. April 2013 erfolge. Das Kontingent verfalle, wenn der Baubeginn nicht vor dem 1. Oktober 2013 erfolgt sei. B. Nachdem mit den Bauarbeiten am 26. September 2013 begonnen worden war, verlangte B._ am 4. Oktober 2013, die Gemeinde habe die Bauarbeiten unverzüglich einstellen zu lassen und die erteilte Baubewilligung als nichtig zu erklären, allenfalls zu widerrufen. Die Gemeinde lehnte diese Anträge mit Schreiben vom 9. Oktober 2013 ab. Sie bestätigte dies mit Verfügung vom 29. Oktober 2013. Dagegen erhoben A._ und B._ am 2. Dezember 2013 Beschwerde an das Verwaltungsgericht des Kantons Graubünden. Dieses trat am 20. Mai 2014 auf die Beschwerde von A._ nicht ein und wies die Beschwerde von B._ ab. C. Gegen den verwaltungsgerichtlichen Entscheid haben A._ (Beschwerdeführerin 1) und B._ (Beschwerdeführer 2) am 23. Juni 2014 Beschwerde in öffentlich-rechtlichen Angelegenheiten erhoben. Sie beantragen, der angefochtene Entscheid sei aufzuheben und es sei festzustellen, dass die Baubewilligung 2012 Nr. 26 der Gemeinde Arosa nichtig sei. Eventuell sei die Gemeinde Arosa anzuweisen, die Baubewilligung zu widerrufen. Subeventualiter sei die Sache zur erneuten Prüfung und Entscheidung an das Verwaltungsgericht zurückzuweisen. D. Die C._ Immobilien AG (heute: C._ AG), die Gemeinde Arosa und das Verwaltungsgericht schliessen auf Abweisung der Beschwerde, soweit darauf einzutreten sei. Das Bundesamt für Raumplanung (ARE) kommt in seiner Vernehmlassung zum Ergebnis, die Baubewilligung sei noch im Jahr 2012 erteilt und noch vor dem 1. Januar 2013 in Rechtskraft erwachsen, so dass sie nicht gemäss Art. 197 Ziff. 9 Abs. 2 nichtig sei. E. Im weiteren Schriftenwechsel halten die Parteien an ihren Anträgen fest.