Der Wettbewerb
Die Aufgaben des Wettbewerbs sind in mehrere Unteraufgaben (Subtasks) aufgeteilt. Diese können Vereinfachungen beinhalten, aber immer entsprechen diese den Komplexitäten einer Lösung. Ein Beispiel: Eine einfache Lösung, die alle Möglichkeiten durchprobiert, schafft nur den ersten Subtask, eine intelligentere mit Optimierungen den nächsten und die beste alle 4. Die Punkte werden nach der Anzahl der geschafften Subtasks vergeben. Im inzwischen offline genommenen interaktiven Scoreboard sah man die Abstufungen sehr deutlich. Bei dem Graphen war auf der y-Achse die Punkteanzahl aufgetragen. So konnte man gut erkennen, dass z.B. immer etwa gleich viele die Subtasks 1, 2 und 3 beim Beispiel Garten erreichten. Eine (gleichmäßige) Aufeilung auf 1-100 Punkte war somit nicht möglich.
Die Dauer eines Wettbewerbs (eines Tages) beträgt 5 Stunden für 3 Aufgaben.
Programmierumgebung
Seit Kanada (2010) bekommen wir während des Wettbewerbs Live-Feedback, d.h. wir können (und sollen, sonst gibt’s keine Punkte) unsere Programme an einen Server senden, der die Programme dann mit den geheimen Testdaten laufen lässt. Die Testdaten sind nun unter dem oben genannten Link verfügbar. Das Interface, das uns auf den Rechnern dazu zur Verfügung steht, nennt sich RunC, und wurde von den Kanadiern entwickelt (die IOI2010 fand in Waterloo, Kanada statt). Es ermöglicht das direkte Kompilieren und Testen (mit minimalen öffentlichen Testdaten sowie eigenen), sowie das Hochladen per Gedit-Plugin (wir hatten Ubuntu 10.04 mit diversen Entwicklungswerkzeugen zur Verfügung) und Kommandozeile. Wer die Programme zu den Aufgaben selbst schreiben und testen will, kann auch mein Shell-Script verwenden, um RunC nicht installieren zu müssen.
Als Programmiersprachen stehen C, C++ und Pascal zur Auswahl, wobei die meisten zu C++ greifen. Der große Vorteil von C++ ist die Standard Template Library (STL), die bei den Aufgaben sehr hilfreich ist. Außerdem wird die STL-Dokumentation von SGI (oben verlinkt) auch zur Verfügung gestellt.
Folgende Programme standen zur Verfügung:
- Compiler: gcc >= 4.4, g++ >= 4.4 und Free Pascal >= 2.4
- Editoren: mcedit, joe, vim, Kate, Kwrite, Emacs, Xemacs, Xwpe, Gedit, Nano, Scite, Geany
- Debugger: gdb und ddd
- Entwicklungsumgebungen: Kdevelop, Lazarus, Code::Blocks, Eclipse mit CDT-Plugin
Ablauf
Um sich den Ablauf des Wettbewerbs ein wenig vorstellen zu können, möchte ich ihn hier ein wenig skizzieren:
Nach dem Erhalt der Aufgaben, die wir in unserer Muttersprache und auf Englisch erhalten, machen sich alle Teilnehmer daran, sich einen Überblick über die Aufgaben zu verschaffen. Anhand der erlaubten Laufzeit und der Anzahl der Subtasks erkennt man recht schnell, welches das Leichteste ist. Zum Aufwärmen und zwecks Motivation machen sich alle (die ich kenne und vermutlich auch alle anderen) daran, diese zu lösen, oder (wie in meinem und vielen anderen Fällen) die beste Lösung zu implementieren, welche einem einfällt. Weiter geht es dann mit den anderen beiden Aufgaben. In meinem Fall blieben dann noch 2 Stunden am Schluss, um noch nach Optimierungen in den Programmen zu suchen. Bei mir misslingt das meist (nicht nur bei der IOI, sondern auch national und sonstwo) oder die Zeit reicht dann nicht mehr, die Lösung zu implementieren (was auch oft vorkommt und sehr schmerzlich ist).
Erster Tag
Üblicherweise sind die Aufgaben des ersten Tages leichter, als die des 2. Tages, was man eventuell auch in der Highscoreliste sehen kann. Denn am ersten Tag erreichten 17 Teilnehmer die maximale Punkteanzahl von 300!
Während des Vormittags kam es ständig zu Regradings, d.h. zur Neubewertung der eingesandten Programme und eventuelle Punkteanpassungen im Nachhinein (wegen fehlerhafter Testdaten). In diesem Ausmaß kam dies noch bei keiner IOI vor, ich war zum Glück von keinem Regrading betroffen. Das interaktive Scoreboard war während des laufenden Wettbewerbs ein Live Scoreboard; man konnte dort aktuell mitverfolgen, wie wir uns mit den Aufgaben schlugen. Leider funktionierte das aber bei etwa 5 Ländern nicht, u.a. Österreich und Albanien. Da es das traditionelle Scoreboard noch nicht gab, kannten wir unsere erreichten Punkte erst einen Tag später.
Kommentare (5)