ACM

ACM Programming Contest

Worum es geht

Die ACM ist die Amerikanische Gesellschaft für Rechnende Maschinen. Diese veranstaltet alljährlich einen Programmierwettbewerb, an dem Teilnehmer aus aller Welt teilnehmen. Ein Team, das aus bis zu 3 Studenten bestehen kann, die noch keinen Bachelor oder vergleichbaren Abschluß haben, bekommt eine Sammlung von Aufgaben mit mathematischen und informatischen Problemen, von denen möglichst viele innerhalb einer gewissen Zeit zu lösen sind. Jedes Team hat dabei nur einen Computer, den man sich teilen muß. Für die Bewertung zählt als erstes die Anzahl der gelösten Aufgaben und als sekundäres Kriterium die aufsummierte Zeit, die zum Lösen einer Aufgabe benötigt wird.

Struktur

Dieses Frühjahr fand die Endausscheidung in San Jose, CA, USA statt, an dem die 50 besten von 1000 Teams teilnahmen. Diese Teams hatten im Herbst des Vorjahres bereits einen der 22 regionalen Vorentscheide gewonnen. Die TU-Darmstadt ist offiziell dem »North Western European Contest« zugeordnet, welches einer der 5 Regionalentscheide Europas ist. Diesem zugehörig sind Holland, Belgien, Irland, England, Schweden, Dänemark, Grönland, Finnland, Luxembourg, Norwegen und Nord-West-Deutschland (Hessen, Niedersachsen, Rheinland-Pfalz, Nordrhein-Westfalen, Hamburg, Bremen, Schleswig-Holstein, Saarland).

Darmstadt

Darmstadt durfte dieses Jahr zwei Teams nach Delft (NL) schicken, nachdem bereits in den letzten Jahren Teams an den Wettbewerben in Delft und Zürich teilgenommen hatten. Durch verstärkte Werbung im Vorfeld konnten dieses Jahr mehr TU-Studierende für den Wettbewerb begeistert werden. Daher fand zum ersten Mal ein interner Qualifikationswettbewerb statt, der neben der Ausscheidung vor allem auch der Vorbereitung der teilnehmenden Teams und dem Sammeln von Erfahrung in der Wettkampfsituation diente. Insgesammt hatten sich 6 Teams gefunden, die am 25. Oktober 1997 gegeneinander antraten: Nach einer kurzen Einführung und einem Testdurchlauf begann gegen 11 Uhr dann der Entscheid: Jedes Team bekam 6 Aufgaben zu mathematischen, Graphen-, Stringbearbeitungs- und Optimierungs- Problemen, für die 5 Stunden Zeit gegeben war. Programmiert wurde unter DOS und Linux mit den Programmiersprachen C, C++ und Pascal. Leider machte letzteres einige Probleme, da Borland-Pascal eben nicht Standard-Pascal ist. Gegen 16:30 Uhr waren dann auch noch einmal alle Ergebnisse überprüft worden, und die Jury nominierte die beiden besten Teams, die nach Delft fahren sollten. Als Preis gab es original T-Shirts vom 1. Darmstädter Programmierwettbewerb sowie die Fahrt nach Delft.

North Western European Contest

Anreise und erster Tag

Die Veranstaltung in Delft fand am letzten Novemberwochenende 22./23.11.1997 statt. Um noch etwas von dem Event zu haben, fuhren wir bereits am Fretiag los. Nach einem gemeinsamen Abend und einer Nacht im Hotel war dann am Samstag Morgen um 10 Uhr Registration an der TU Delft. Nach einer Eröffnungsrede gab es zwei Vorträge über das letztjährige Final in den USA und über »electronic comerce« im Internet. Nach dem Mittagessen und zwei weiteren Vorlesungen über »zero-knowledge«-Beweise und »repetetive strain injuries« ging es an die Rechner, um mit dem System vertraut zu werden. Die Software hatte zwar noch einige Fehler, was Team 2 aber nicht daran hinderte, den Testdurchlauf zu gewinnen. Als Abschluß des Tages gab es noch ein gemeinschaftliches Abendessen.

Der (Sonn-)Tag

Sonntag war dann der große Tag: Nach dem Frühstück im Hotel gab es wieder eine Begrüßung mit letzten Änderungen, so daß pünktlich gegen 11:00 Uhr der Startschuß fiel: 41 Teams machten sich an die 8 Aufgaben, für die 5 Stunden Zeit vorgesehen waren. Sobald eine Aufgabe erfolgreich gelöst war, bekam das Team einen farbigen Luftballon als Erkennungszeichen. Bis eine Stunde vor Ende konnte man auf einer Rangliste den Vortschritt der Teams online mitverfolgen. Um die Spannung zu erhöhen, wurden 30 Minuten vor Schluß dann auch keine Ballons mehr verteilt, so daß die Plazierung bis zur Verkündung geheim blieb.

Nach 5 Stunden fand man dann endlich wieder Zeit, das ausgefallene Mittagessen nachzuholen und mit anderen die Probleme zu diskutieren. Die institutseigene Bar ließ die Stunde Wartezeit schnell vergehen und es nahte der Höhepunkt: Zwei Teams würden die Chance bekommen, Ende Februar nach Atlanta zur Weltendentscheidung zu fahren. Die Plätze 10 bis 4 wurden verlesen und erst als auch Team 2 aus Darmstadt noch nicht den 3. Platz belegte, war die Spannung genommen: 5 Aufgaben in 619 Minuten reichten noch für den 2. Platz nach dem Gewinnerteam aus Schweden mit 6 Aufgaben in 594 Minuten.

Ausblick

Falls Du Interesse gefunden hast und auch einmal zusammen mit deinen Kommiliton(inn)en euer Können unter Beweis stellen wollt, meldet euch mal bei Henning Pagnia oder Ulrik Schroeder. Wenn wieder so reges Interesse besteht wie dieses Jahr, werden wir sicherlich erneut eine Vorentscheidung für Darmstadt machen.

Den nächsten Wettbewerb gibt es bereits im kommenden Sommersemester 1998, wieder mit der Chance eine Traumreise zu den Finals (diesmal wohl nur in Holland) zu gewinnen. Weitere Informationen dazu gibt es dazu schon auf der ACM Contest Page der TU

Zum Üben gibt es sehr viele Aufgaben auf den WWW-Servern der Universitäten, die solche Wettbewerbe ausrichten. Ein kleine Auswahl an URLs gibt es unter ACM Links