Der ACM International Programming Contest 1997-98

Rückblende

Am 23. November 1997 belegten wir, das Team der Universität Ulm, den zweiten Platz beim ACM Southwestern European Programming Contest 1997 (SWERC '97) und qualifizierten uns damit für die Weltmeisterschaft 1998. Nach drei weiteren Monaten harten Trainings und unzähligen Probewettkämpfen flogen wir dann im Februar 1998 zu den ACM World Finals nach Atlanta. Begleitet wurden wir von einem ganzen 'Fan Club' von Freunden, die begeistert von unserer WM-Qualifikation waren.

Dienstag, 24. 2. , Flug und Ankunft in Atlanta

Flughafen Stuttgart,14:00 Uhr. Unser Flugzeug rollt an. In acht Stunden werden wir in Atlanta ankommen. Wir, das sind das eigentliche Team (Ralf Gandy, Thorsten Quell, Christian Ehrhardt, Ralf Engels und Stefan Schonger) sowie Marc Meister, Martin Gaus, Walter Guttmann, Martin van Rijswick und die beiden Vorjahressieger Gerhard Lutz und Falk Bartels. Mark Dettinger, ebenfalls Vorjahressieger und Organisator des SWERC '97, Sandra Siehler und Berno Kneer befinden sich bereits seit zwei Wochen in den USA. Melanie Much wird am Freitag nachkommen. Für einige von uns ist es (nach Philadelphia '96 und San José '97) bereits die dritte Amerikareise, die wir der Association for Computing Machinery (ACM) zu verdanken haben.

Atlanta, 17:00 Uhr.  Für die nächsten Tage wird das Marriott Marquis Hotel, das von der ACM als offizielles Contest Hotel auserkoren wurde, unser Zuhause sein. Kein schlechtes Hotel, wie wir schnell feststellen. Wir haben ein Zimmer im 25. Stock mit Blick über Atlanta, dazu Whirl-Pool und Fitness-Studio.
 

Die Ulmer Delegation im Marriott Marquis Hotel in Atlanta Von links nach rechts: Hinten: Martin Gaus, Walter Guttmann, Ralf Engels, Marc Meister, Mark Dettinger, Stefan Schonger, Berno Kneer, Martin van Rijswick, Falk Bartels. Vorne: Thorsten Quell, Melanie Much, Sandra Siehler, Christian Ehrhardt, Ralf Gandy, Gerhard Lutz

Mittwoch, 25.2., Regional Contest Directors' Meeting

Für Mark steht heute das Regional Contest Directors' Meeting auf dem Programm, wo über die Zukunft des ACM Contests diskutiert wird. Die gestellten Aufgaben müssen zum Beispiel im Laufe der Jahre an die Erfordernisse der Software-Industrie angepasst werden, so dass im ACM Contest auch diejenigen Fähigkeiten geprüft werden, die in der Praxis relevant sind. So erforderten die Programmieraufgaben der 80er Jahre vor allem Kenntnisse in Mathematik und Physik. In den 90ern ging der Trend dann zu logischen, graphentheoretischen und algorithmischen Problemen. Für das nächste Jahrzehnt ist ein langsamer Übergang zu graphischen und interaktiven Programmen geplant. Dies erfordert jedoch entsprechende Anpassungen der Regeln. Sollen z.B. Bonuspunkte für ansprechende graphische Gestaltung vergeben werden?
Ein weiterer zentraler Punkt der Diskussion sind Überlegungen, wie der Wettbewerb auf weitere Länder ausgedehnt werden kann. So gab es 1997 z.B. das erste Mal einen Regional Contest in Indien. Und im November 1998 wird nun auch Afrika seinen Champion im Programmieren ermitteln. Ausrichter wird die Al Akhawyn University in Marokko sein.

Für unser restliches Team gibt es heute noch nicht viel zu tun, also nutzen wir die Zeit für eine Stadtbesichtigung. Sehenswert sind z.B. das World of Coca Cola Museum, Underground Atlanta (eine gigantische Shopping Mall), CNN und der Centennial Park.
 

Donnerstag, 26. 2. , IBM Tech Trek

Heute steht der "IBM Tech Trek" auf dem Programm. Im nicht weit entfernten Westin Plaza Hotel laufen - nachdem ein Mittagessen für uns organisiert wurde - verschiedene Programme parallel: e-Business, Deep Blue, C++, Java.
Im Vorfeld darf man sich für zwei davon entscheiden.
Deep Blue
Deep Blue ist ein massiv-paralleler Rechner, der Schach auf Großmeisterniveau spielen kann. Berühmt wurde er 1997, als er ein Match über sechs Partien gegen Garri Kasparov gewann. Leider war aber weder der Vortrag tief noch der Vortragende (einer der Entwickler) blau. So blieb es bei einem unterdurchschnittlichen, sehr allgemein gehaltenen Vortrag über Computerschach, der uns nicht den erhofften tieferen Einblick in die Soft- und Hardware von Deep Blue bescherte.
Mittlerweile hat Deep Blue übrigens schwer nachgelassen: er berechnet nur noch Wettervorhersagen.
Java
Im Java-Teil sollte vornehmlich IBM's hauseigenes Produkt Visual Age for Java vorgestellt werden. Nachdem aber die Vortragende die Programmierumgebung samt dem Betriebs(störungs)system (Windows) ins Nirwana schickte, verließen einige den Tatort.
e-Business
Tja, dieser Vortrag war anscheinend der beste. (Und wir hatten uns natürlich für die zwei falschen entschieden.) Mit dem Stichwort e-business bezeichnet man die zukünftige Verwendung des Internets als virtuelles Kaufhaus. Da Geld dann nur noch ein Stück elektronische Information sein wird, müssen Mechanismen entwickelt werden, um elektronisches Geld (e-money) sicher übertragen zu können und außerdem vor Fälschung und Kopieren zu schützen.
Das Westin Plaza Hotel
Mit seinen 72 Stockwerken ist das zigarettenförmige Hotel an sich sehenswert. Interessant ist auch das Schild im Treppenhaus im 70. Stock: Emergency exit 4th floor.
 

Freitag, 27. 2. , Practice Session und Visual Age Contest

Der letzte Tag vor den Finals. Nachmittags um 3:00 Uhr ist die Practice Session im "Marquis Ballroom" angesetzt, wo man sich unter Contest-Bedingungen, aber mit einfacheren Aufgaben, an die Rechner, die Installation und das Judging-System gewöhnen kann.

Nachdem dort noch einige offene Fragen geklärt wurden, bleiben wir gleich am Rechner für den "Visual Age for Java Contest", der dort zum zweiten Mal in dieser Form abläuft. Außer Konkurrenz zum eigentlichen Contest - aber mit netten Preisen - liegt bei diesem Wettbewerb mehr Gewicht auf der Oberflächenprogrammierung. Auch bei der Bewertung zählen eher subjektive Dinge wie Aussehen, Funktionalität und sinnvolle Erweiterungen. Wie oben gesagt, es ist bereits in der Diskussion, solche Elemente in Zukunft in den Hauptwettbewerb aufzunehmen.
Konkret sollte nun ein Taschenrechner (ähnlich dem Windows calc) entwickelt werden. Dabei waren schon einige Komponenten vorgegeben, die man sich erst einmal anschauen und dann erweitern mußte. Obwohl wir einige kleine  Probleme hatten (die Vorbereitung war schwierig, weil es noch keine Aufgaben aus vergangenen Contests gab), schlagen wir uns gar nicht schlecht (manche Teams schicken hier gar nichts ab). Unter die ersten drei kommen wir dann aber doch nicht...
 

Samstag, 28. 2. , Der große Tag

Marriott Marquis, Imperial Ballroom, 10:00 Uhr: Der Contest.

In unzähligen lokalen, nationalen und subregionalen Vorausscheidungen haben Zigtausende von Teams aus allen Teilen der Welt bereits ihr Können unter Beweis gestellt. Auf der vorletzten Ebene (den Regional Contests) waren es immerhin noch 1250 Teams. Die 54 besten treten nun zum Showdown an. Gespannt sitzen die 162 Teilnehmer vor den verschlossenen Umschlägen mit den Aufgaben. In großen Mengen wurden zuvor schon Bücher und Ordner mit Algorithmen, mathematischen Formeln und Beschreibungen der C-Standardbibliotheken in den Ballsaal des Marriott Hotels gebracht.  Pünktlich der Start, 54 mal das gleiche Geräusch, als die Umschläge aufgerissen werden. Acht Probleme sind zu bearbeiten.

Nach ca. 45 Minuten liefert das erste Team eine Lösung ab. Wir selbst bekommen nach 69 Minuten unser erstes "Accepted" für das Problem "Page Selection by Keyword Matching", einer kleinen Suchmaschine fürs WWW. Wir liegen auf Platz 8, bisher scheint es gut zu gehen.

Wir bearbeiten drei Probleme parallel. Bei einem ("Flight Planning") ist der Treibstoffverbrauch eines Passagierflugzeuges zu minimieren. Abhängig von den Windverhältnissen und dem zusätzlichen Verbrauch beim Steigflug und beim Flug in einer für die Triebwerke ungünstigen Höhe, muß die zu fliegende Höhe geschickt berechnet werden. Beim zweiten ("Towers of Powers"), einer mathematisch an sich einfachen Aufgabe, liegt die Schwierigkeit vor allem in der komplizierten Formatierung der Ausgabedaten. Im dritten ("Spatial Structures") geht es um Datenkompression.
Im Wechsel arbeiten immer zwei auf Papier und einer am Rechner. "Flight Planning" können wir letztendlich lösen, die anderen beiden werden aus uns (zur Contest-Zeit) unerklärlichen Gründen von der Jury mit "Time-Limit exceeded" und "Wrong Answer" bewertet.

Immer wieder drucken wir unsere Lösungen aus und verbessern sie. Die Zeit läuft davon. Fünf Stunden können verdammt kurz sein. Gegen Ende versuchen wir uns noch an "Crystal Clear", einer geometrischen Aufgabe, in der die Isolationskapazität von Kristallen berechnet werden muß. Doch die Zeit reicht nicht mehr, um die Aufgabe zu beenden.

Nach 4 Stunden wird die Rangliste eingefroren, in der letzten halben Stunde werden auch keine Luftballons mehr für gelöste Aufgaben ausgeteilt. Dadurch ist am Ende nicht klar, welches Team nun gewonnen hat, und die Spannung zieht sich hin bis zur Siegerehrung am Abend.

Marriott Marquis, 18:00 Uhr: Siegerehrung

Bei der Siegerehrung am Abend ruft Bill Poucher, International Contest Director und Professor für Informatik an der Baylor University in Texas, die Teams der Top 10 von hinten nach vorne auf die Bühne. Die Top Ten 1998 lautet:

		Universität	Land	Gelöste Probleme	Akkumulierte Zeit
1		Charles University Prague	Tschechien	6	919
2		St. Petersburg University	Russland	6	1021
3		University of Waterloo	Kanada	6	1026
4		University of Umeå	Schweden	6	1073
5		MIT	USA	6	1145
6		Melbourne University	Australien	6	1153
7		Tsing Hua University - Peking	China	5	743
8		University of Alberta	Kanada	5	758
9		Warsaw University	Polen	5	780
10		Politehnica University Bucharest	Rumänien	5	813

Unsere zwei Lösungen in 292 Minuten reichen immerhin noch für einen Platz im Mittelfeld: Platz 29. Das zweite deutsche Team bei der WM, die TU Darmstadt, landet mit zwei Lösungen in 487 Minuten auf Platz 37. Auffällig ist, daß die US-Universitäten dieses Jahr nur noch einmal in der Top 10  vertreten sind, die Osteuropäer dagegen viermal. Dieser Trend scheint sich von Jahr zu Jahr zu verstärken.

Unter der akkumulierten Zeit versteht man die Summe der Abgabezeiten. Wir lösten die erste Aufgabe nach 69 Minuten, die zweite nach 223 Minuten. 69 + 223 = 292.

Die Speedzone

Vor dem Marriott Marquis Hotel, 19:00 Uhr. Wir besteigen die Busse, die uns zur "Malibu Speedzone" bringen sollen, wo die Abschlußfeier stattfinden wird.  Was uns dort genau erwartet, wissen wir nicht genau. Go-Kart-Rennen und Spielautomaten, so kursieren die Gerüchte.  Komisch ist allerdings, daß kontrolliert wird, wer einen Führerschein besitzt. Für ein paar mickrige Go-Karts?  Außerdem erhalten wir einen kleinen Umschlag mit Informationen zu den Gefahren von Autorennen und einer Erklärung,  daß der Veranstalter für keine Verletzungen haftbar ist, die wir uns durch selbstverschuldete Unfälle zuziehen.

Am Eingang der Speedzone geht es dann los. Jeder bekommt eine Magnetkarte mit einem Guthaben von 80 Dollar ausgehändigt. Da die Rückkehr schon für ein Uhr geplant ist, haben wir nicht sehr viel Zeit. Deshalb stürmen wir schnell herein.

Das Hauptgebäude hat einen Bereich mit Spielautomaten, eine Bar und ein paar Stände für Souvenirs. IBM hat den ganzen Komplex gemietet und auch ein Buffet mit vielen leckeren Sachen aufgestellt. Die Spielautomaten, wie auch die Souvenirs, können mit der Magnetkarte bezahlt werden.

Draußen befinden sich die Rennbahnen. Dort sind allerdings keine mickrigen Go-Karts, sondern eher kleine Formel-1-Rennwagen. Mit einem Motor, der die Räder durchdrehen läßt, und Bremsen, die wie Beißzangen zugreifen. Auf manchen Strecken kann man allein gegen die Zeit fahren, auf anderen richtige Rennen gegeneinander. Insgesamt geht alles glimpflich ab. Nur selten muß das Personal eingreifen, beispielsweise, als Stefans Wagen nach einer kleinen Kollision Feuer fängt. Doch schon in wenigen Minuten ist der Wagen ausgewechselt und es kann weitergehen.

In einem Nebenraum hat IBM den Supercomputer Deep Blue für seinen letzten Auftritt in der Öffentlichkeit aufgestellt, bevor er - wie oben schon gesagt - zum Wetterbericht-Ersteller degradiert wurde. Hier konnte man an mehreren Terminals simultan gegen ihn spielen, auf jedem Terminal gegen einen seiner Prozessoren. (Gegen Kasparov wurden damals alle 1000 Prozessoren gleichzeitig eingesetzt.) Soweit wir mitbekommen haben, blieb Deep Blue aber an diesem Abend trotzdem ungeschlagen. Ein Prozessor reicht eben für den Normalspieler schon mehr als aus.

Insgesamt wird der Abend zum krönenden Abschluss der WM, der uns die Anspannung des Wettkampfs (und ein bisschen die Enttäuschung ueber unser Ergebnis) fuer ein paar Stunden vergessen lässt. Mit vielen Teams tauschen wir E-Mail-Adressen aus, um in Kontakt bleiben zu können.

Sonntag, 1. 3. , Abreise von Atlanta

Bei der Abreise aus Atlanta sind wir immer noch in Gedanken mit den Aufgaben von gestern beschäftigt. Wenn wir doch dies anders gemacht hätten oder das...vielleicht wäre ja alles ganz anders gelaufen. Andererseits: Platz 29 von allen Studenten weltweit ist ja nicht ganz schlecht. Und nächstes Jahr haben wir ja wieder eine Chance. Die WM 1999 wird in Eindhoven, Holland, ausgetragen werden, zum ersten Mal in Europa. Und selbstverständlich wollen wir da wieder dabei sein.