Der Wettbewerb


i-7ed849fb807176065908c0d44d17eb42-Wettbewerb-thumb-250x166.jpg

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

Quelle

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.

1 / 2 / 3 / 4

Kommentare (5)

  1. #1 Maxi
    August 23, 2011

    Wow! Gratulation, dass du soweit gekommen bist, Sebastian!
    Ich habe noch nie etwas von der “IOI” gehört, das hat sich nun geändert, danke für den Artikel.

    Bin schon gespannt, wie man solche Probleme löst 😀

  2. #2 Gotha Plast
    August 24, 2011

    Super Bericht,
    kannte die IOI auch noch nicht und die Probleme die gelöst werden sollen
    haben es schon in sich (vorallem Tag 2).
    Auch wenn der Artikel nicht von dir ist Marcus, so wär es trotzdem super, wenn du die wirklich groben Rechtschreibfehler an manchen Stellen entfernen würdest.

    Grüße
    Gotha

  3. #3 Marcus Frenkel
    August 24, 2011

    @Gotha Plast
    Danke für den Hinweis, ich habe die schlimmsten Fehler beseitigt. Beim Querlesen fallen die leider nicht unbedingt auf…;)

  4. #4 Dr. Webbaer
    August 24, 2011

    Dr. W rät regelmäßig zum Einsatz einer Rechtschreibprüfung. Witzigerweise wird das auch von professionellen Schreibkräften oft unterlassen. – Die Authentizität wird nämlich nicht “wirklich” erhöht, auch was die Hochtalentierten betreffen tut.

  5. #5 Christian Berger
    August 24, 2011

    Schön mal auch einen Artikel zum Thema Informatik in einem Informatikblog zu lesen. Trau Dich doch.