ACM Programmierwettbewerb an der FAU

Wie läuft so ein Wettbewerb ab?

Der ICPC ist ein Programmierwettbewerb. Das heißt, dass den teilnehmenden Teams bestimmte Aufgaben gestellt werden, zu deren Lösung Programme geschrieben werden müssen. Jedes Team besteht aus bis zu drei Studenten einer Universität; jede Uni darf mehrere Teams zum Regionalcontest (zur Zeit gehören wir zu Nordwesteuropa) entsenden.

Der eigentliche Wettbewerb dauert 5 Stunden. Zu Beginn des Wettbewerbs erhält jede Mannschaft die Problembeschreibungen. Meistens sind es zwischen acht und elf Problemen, die gelöst werden sollen. Am Ende gewinnt die Mannschaft, die die meisten Probleme lösen konnte. Haben zwei Teams gleich viele Probleme knacken können, entscheidet die benötigte Zeit über die Platzierung.

Innerhalb der fünf Stunden teilt man sich zu dritt einen Computer, an dem die Programme geschrieben werden. Während einer programmiert, denken die beiden anderen über weitere Probleme nach, um sie dann, sobald der Rechner frei wird, selbst reinzuhacken. Das ganze erfordert einen hohen Teamgeist und gute Abstimmung untereinander, denn es ist Weniges so unbefriedigend, wie wenn man zu einem Problem die Lösung gefunden hat, aber erst noch 15 oder 20 Minuten warten muss, bis der Computer frei ist und man sie auch programmieren kann.

Wann gilt eine Aufgabe als gelöst?

Fast alle Probleme sind von der Bauart, dass ein Programm erstellt werden muss, das von stdin eine Eingabe liest, die Eingabe verarbeitet und dann eine entsprechende Ausgabe nach stdout schreibt. Neben den Problembeschreibungen in Prosa, die man zu Beginn des Wettbewerbs in drei Kopien ausgehändigt bekommt, werden für jedes Problem noch mehrere Beispielein- und -ausgaben mitgeliefert, anhand derer man sehen kann, ob sein Programm ungefähr das tut, was es tun soll.

Wenn man dann irgendwann so weit ist, dass man denkt, das Problem gelöst und alle Spezialfälle bedacht zu haben, schickt man den Quelltext per Web-Formular an einen Auswertungsserver, der das Programm selbst kompiliert und mit Hilfe geheimer Testfälle überprüft, ob es korrekt ist. Auf einer Übersichtsseite kann man dann den Status der Einsendung abfragen. Im besten Falls bekommt man ein "Accepted" und kann sich an die nächste Aufgabe machen. Dauert die Ausführung des Programms zu lange (wobei die genauen Zeit-Limits für die Aufgaben meist geheim sind), erhält man ein "Time-Limit". Ist das Programm schlicht falsch, sagt der Server "Wrong Answer".

Die auf ein "Wrong answer" folgende Fehlersuche kann dann auch mal frustrierend sein, weil man überhaupt nicht weiß, was genau falsch ist: vielleicht bloß die Formatierung der Ausgabe, oder man hat tatsächlich etwas übersehen.

In welcher Sprache darf man programmieren?

In der Regel darf man die Programme in C, C++, oder Java erstellen. Beim Wintercontest konnte man sich teilweise noch andere Sprachen wünschen.

Wo gibt es Beispielprobleme?

Am besten schaust Du dir die Problemstellungen der letzten Contests an. Gute Trainingsmöglichkeiten bieten Online-Judges wie UVa und Spoj oder auch Contest-Plattformen wie TopCoder oder USACO.