Wie läuft so ein Wettbewerb ab?

Der ICPC ist ein Wettbewerb, bei dem die Teilnehmer (beliebiger Fachrichtungen) in der vorgegebenen Zeit möglichst viele der gestellten Aufgaben lösen müssen. Die Probleme sind oft mathematischer oder algorithmischer Natur, wobei die Schwierigkeit meist darin besteht, einen geschickten Lösungsansatz zu entwickeln. Als Lösung wird ein kleines Programm geschrieben, das auf einer Reihe von Testfällen die richtige Lösung berechnet. Auch wenn der ICPC ein “Programmierwettbewerb” ist, gehört Coden zwar dazu, spielt aber eine untergeordnete Rolle.

Ein Team besteht aus bis zu 3 Studenten. Der eigentliche Wettbewerb dauert 5 Stunden. Zu Beginn des Wettbewerbs erhält jedes Team die Problembeschreibungen. Meistens sind es gut zehn Problemen, die gelöst werden sollen. Am Ende gewinnt das Team, das 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.

Wie sieht so eine Aufgabe aus?

Eine Aufgabe enthält meistens eine kurze Geschichte, eine daraus resultierende Problembeschreibung mit exakt spezifizierter Ein- und erwarteter Ausgabe sowie ein paar Beispielen anhand derer man einen ersten Funktionalitätscheck durchführen kann. Als Lösung muss ein Verfahren entwickelt werden, das das gegebene Problem richtig und effizient löst. Oft sind hierbei grundlegende Kenntnisse von Dynamischer Programmierung, Graphalgorithmen oder Geometrie von Hilfe, jedoch sind Aufgaben häufig ohne Spezialwissen lösbar. 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. Häufig lässt sich ein Problem auf naive Weise theoretisch lösen, jedoch erfordert ein gesetztes Laufzeitlimit, dass die Verarbeitung geschickt vorgeht, um eine effiziente Verarbeitung zu erreichen. Beispielsweise kann das Sortieren der Daten und Verarbeiten in der richtigen Reihenfolge, die Komplexität reduzieren.

Ein fertiges Programm lädt man als Quelldatei auf einem Server hoch. Dort wird es ausgeführt und mit mehreren geheimen Testfällen auf Richtigkeit überprüft. Wird jeder Testfall in der geforderten Zeit bestanden, wird die Aufgabe als gelöst gezählt und das Team erhält einen Punkt. Andernfalls erhält das Team eine Antwort (Timelimit, Abgestürtzt oder Falsch) und kann entsprechend nachbessern. Ein Problem kann beliebig oft versucht werden, jedoch wird im Falle des Lösens jeder vorherige Fehlversuch mit einer kleinen Strafzeit gewertet.

Ich hab doch keine Ahnung. Ist das etwas für mich?

Hast du Spaß am Tüfteln und Knobel? Dann ja! Es gibt Aufgaben, die “ohne” besonderes Wissen lösbar sind, ansonsten ist meist Schulmathematik ausreichend. Zur Implementierung ist natürlich eine der geforderten Programmiersprachen notwendig. Allerdings seid ihr in einem Team (wir können euch auch Informatikaffine Teamkollegen suchen) und ein Semester AuD o.ä. lehrt euch ausreichend Kenntnisse der Sprache (generell würde jeder Stylechecker bei ICPC Programmen eine Krise bekommen).

In welcher Sprache darf man programmieren?

Programme müssen meist in C++, Java oder Python erstellt werden. Manchmal sind auch andere Sprachen (Haskell, Kotlin) erlaubt.

Qualifikation? Struktur? Weltweiter ICPC?

Generell ist der ICPC ein weltweiter Wettbewerb über mehrere Stufen. Auf der untersten Ebene kann aber jeder auch nur zum Spaß teilnehmen. An der FAU bieten wir im Januar den FAU Wintercontest an. Dieser ist ein inoffizeller Wettbewerb, der von uns für euch angeboten wird. Die Schwierigkeit der Aufgaben liegt unter dem GCPC, sodass er auch besonders für Erstsemestler interessant ist. Im Sommer gibt es dann den GCPC. Auch hier kann jeder unverbindlich teilnehmen. Zeitgleich findet der GCPC an gut 10 Universtäten in ganz Deutschland statt. Aus den guten und motivierten Teilnehmern der FAU suchen wir 6-9 Studierende aus, die mit uns zum NWERC fahren und dort auf europäischer Ebene gegen andere Unis antreten. Wer es schafft unter die Besten zu kommen, qualifiziert sich für die Worldfinals.

Wo gibt es weitere Informationen oder Beispielprobleme?

Du hast hier hoffentlich bereits eine grobe Vorstellung von dem Wettbewerb. Bei weiteren Fragen wendest du dich am Besten an ehemalige Teilnehmer oder schickst uns eine Mail. Zu ein paar weiteren technischen Details gibt es noch die Regelseite. Für Beispielprogramm schaust du dir am Besten die Problemstellungen der letzten Contests an. In unserem Online-Judge kannst du diese auch selbst versuchen. Gute Trainingsmöglichkeiten bieten ansonsten Online-Judges wie https://open.kattis.com/ , UVa und Spoj oder auch Contest-Plattformen wie TopCoder oder USACO.