International Collegiate Programming Contest

Die folgende Einführung stammt ursprünglich von Robert Will von der Uni Ilmenau.

1. Überblick

Die Association of Computing Machinery (ACM), die größte Informatikervereinigung der Welt, veranstaltet jährlich eine Programmierweltmeisterschaft für Studenten. Hierzu werden nach Beginn des Wintersemesters zunächst lokale, dann regionale Wettbewerbe ausgetragen. Die Besten der Welt treffen schließlich bei den World Finals im März des nächsten Jahres irgendwo in den USA aufeinander.
 

2. Aufgaben

Die 8 Aufgaben die innerhalb 5h zu lösen sind, werden aus verschiedenen Bereichen der Informatik kommen. Bereiche, die dabei sein werden, stehen noch nicht fest. Könnten aber wie in folgender Tabelle die der Uni Ulm entnommen ist aussehen.
Bereich  Beispielprobleme 
Backtracking  8-Damen-Problem
Springertour auf Schachbrett 
Graphenprobleme  Kürzeste Route zwischen 2 Städten finden, wobei eine Landkarte gegeben ist 
Testen, ob ein gegebener gerichteter Graph einen Zyklus enthält 
Computational Geometry  Bestimmen, ob sich zwei gegebene Strecken schneiden oder nicht 
Konvexe Hülle eines Polygons bestimmen 
Dynamisches Programmieren  Rucksackproblem
Optimale Klammerung einer Kette von Matrixmultiplikationen A1 * A2 * ... * An, so dass die Anzahl der elementaren Multiplikationen minimiert wird 
Zahlentheorie  Summe aller echten Teiler einer gegebenen Zahl berechnen 
Alle Primzahlen p mit a <= p <= b ausgeben 
Parser/Compilerbau  Eingabe: ein arithmetischer Ausdruck als String
Ausgabe: das Resultat dieses Ausdrucks
Beispiel: Eingabe: "4+3*(7-2)", Ausgabe: 19

3. Ablauf des Wettbewerbs

Ein Team besteht aus 3 Personen. Zu jeder Aufgabe (bzw. zu so vielen wie in 5 Stunden eben möglich) soll ein Programm geschrieben werden, das diese Aufgabe löst. Wer glaubt, sein Programm sei korrekt, der schickt es mit dem Befehl submit problemname.(c|C|pas) an die Jury. Die Jury compiliert das Programm, testet es dann mit Beispieleingaben und schickt schließlich eine der folgenden Meldungen per e-mail zurück.
Meldung  Bedeutung 
Accepted  Programm ist als korrekt akzeptiert. Gratuliere. 
Wrong Answer  Programm liefert falsche Antwort 
Presentation Error  Algorithmus ist im Prinzip richtig, aber Ausgabe entspricht nicht der gegebenen Spezifikation 
Time-Limit exceeded  Algorithmus ist zu langsam.
D.h. Ausführungszeit für Beispieleingabe >> 60 sec 
Run-Time Error  Programm stürzt ab 
Compile-Time Error  Programm läßt sich nicht compilieren

Man hat beliebig viele Versuche, bis man eine "Accepted"-Meldung erhält. Allerdings bekommt man für jeden Fehlversuch 20 Strafminuten zur benötigten Programmierzeit addiert. Achtung: Das heißt nicht, das man dann nach 4:40 h aufhören muss. Man darf auf jeden Fall 5 Stunden lang programmieren. Es wird dann aber so gewertet, als hätte man 5:20 h gebraucht.

4. Wertung

Sieger ist, wer die meisten korrekten Programme schafft. Bei Gleichstand entscheidet die Summe der Zeiten, zu denen die korrekten Programme mit submit abgeschickt wurden. Je niedriger diese Summe, desto besser. Außerdem werden noch 20 Strafminuten pro Fehlversuch angerechnet. Fehlversuche werden allerdings nur für Programme gezählt, die man letztendlich doch als korrekt gewertet bekam.

5. Tips zur Vorbereitung

Die beste Vorbereitung besteht darin, Probleme vergangener ACM-Wettbewerbe zu lösen, um eine Vorstellung von der Art der Aufgaben zu bekommen. Hier sind ein paar Links die Euch vielleicht weiterhelfen.

6. Empfohlene Literatur zur Vorbereitung und im Wettbewerb