Vor einiger Zeit hatte ich ja auf die diesjährige Informatik-Olympiade in Pattaya hingewiesen. Die ist nun schon einige Zeit vorbei – und hier kommt endlich der versprochene Bericht dazu. Geschrieben hat ihn Sebastian Wagner, ein Teilnehmer der Olympiade.
Meine Intuition, diesen Artikel (der sicherlich nicht der letzte ist) zu schreiben, war, die Informatik-Olympiade etwas bekannter zu machen. Wie Marcus hier schon geschrieben hat, hat kaum jemand schon davon gehört, obwohl sie seit 23 Jahren ausgetragen wird und Informatik im Alltag eigentlich immer präsenter wird. In Österreich haben wir zusätzlich noch wenig Nachwuchsinformatiker und in der Öffentlichkeit sind wir sowieso total unwichtig (im Gegensatz z.B. zum BWINF/DE). Da sind hauptschulinterne Wettbewerbe eines Bezirkes viel wichtiger als dieser internationale Wettbewerb.
Ich durfte dieses Jahr zum ersten Mal an der internationalen Informatikolympiade teilnehmen. Aus diversen Erzählungen über frühere IOIs von meinen Begleitern ist mir bekannt, wie die Wettbewerbe früher abliefen.
Die Internationale Informatik Olympiade (IOI) ist einer der international angesehensten Informatik-Wettbewerbe. Sie wird jedes Jahr in einem anderen Land, dieses Jahr in Thailand, im Sommer veranstaltet. Heuer fand sie vom 22. bis 29. Juli statt.
Die Aufgaben sind von algorithmischer Natur, weshalb die Teilnehmer einige Fähigkeiten aufweisen müssen:
- Problemanalyse
- Erstellen von Algorithmen
- Datenstrukturen
- Programmierung
- Testen
Teilnehmen dürfen alle Länder1, die maximal 4 Schüler zur IOI senden dürfen. Die Auswahl dieser 4 Schüler geschieht meist über nationale Wettbewerbe. In Deutschland über den Bundeswettbewerb-Informatik, in Österreich über die Österreichische Informatik Olympiade2 und in der Schweiz über die Swiss Olympiad in Informatics.
Das erste Zwölftel in der Highscoreliste bekommt eine Goldmedaille (heuer 26), die nächsten 2 Zwölftel eine Silberne (51), und 3 Zwölftel eine Bronzemedaille (75). Ich habe noch niemanden gefunden, der diese Aufteilung unfair findet, denn somit bekommt die Hälfte aller Teilnehmer eine Medaille und es entscheiden nur an den Grenzen zwischen den Medaillen einzelne Punkte, denn die Leistungen, die von allen Olympioniken erbracht werden und wurden, sollten in hohem Maß gewürdigt werden.
Die Teilnehmer
Jedes Land darf
- 2 Team-Leader: einen Delegation Leader und den Stellvertreter (Deputy Leader),
- bis zu 4 Contestants (Wettbewerbsteilnehmer),
- und einen Gast (Visitor)3
zur IOI senden.
Da noch lange nicht alle Länder der Erde teilnehmen, wächst verständlicherweise die Anzahl der Teilnehmer jedes Jahr. 79 Länder nahmen heuer teil (mit mindestens einem Contestant) und 307 Contestants. Auf dem Bild ist leider nur ein Ausschnitt aller Teilnehmer zu sehen, während des Auflugs im Nong Nooch Tropical Garden.
Der erfolgreiche Gennady
Es ist schon fast ein Naturgesetz, dass Gennady Korotkevich gewinnt. Mit 3 ersten Plätzen und 4 Goldmedaillen ist er der erfolgreichste Informatik-Olympionike aller Zeiten4.
1.6286645% Damenanteil
Leicht unterrepräsentiert war die Gruppe der Frauen. Bangladesch, Georgien, Indonesien, Vietnam und Zypern hatten jeweils eine weibliche Repräsentantin. Der Anteil der Frauen unter den Leadern war aber deutlich höher!
Programm
- Freitag, der 22. Juli: Ankunft und Registrierung
- Samstag, der 23. Juli: Eröffnungszeremonie
- Sonntag, der 24. Juli: Erster Wettbewerbstag
- Montag, der 25. Juli: Erster Exkursionstag (Nong Nooch Tropical Garden)
- Dienstag, der 26. Juli: Zweiter Wettbewerbstag
- Mittwoch, der 27. Juli: Zweiter Exkursionstag (Ancient City, bzw. The Grand Palace, Wat Prakaew & Vimanmek Manison)
- Donnerstag, der 28 Juli: Abschlusszeremonie
- Freitag, der 29. Juli: Abfahrt
Die Organisation
Die Organisation der diesjährigen IOI war sehr gut, bis auf den 1. Wettbewerb, aber dazu später mehr. So eine gute Organisation war bis jetzt nicht selbstverständlich, die IOI in Thailand zieht einen Schlussstrich unter die mangelhafte Organisation, schlechtes Essen, mangelhafte Unterkunft etc.; Schwierigkeiten, mit denen die vorigen IOIs in Erinnerung blieben.
Untergebracht wurden alle Teilnehmer in den Hotels der berühmten Royal Cliff Hotels Group (Beach und Grand Hotel) in Pattaya City, einer Touristenmetropole. Die Zeremonien sowie die Wettbewerbe wurden in den Räumlichkeiten des riesigen “PEACH” abgehalten, welches auch zu dem Hotelkomplex gehört. Das Areal liegt direkt am Golf von Thailand, mit seinem sehr warmen Wasser mit vielen Quallen. Zum Glück gab’s noch 3 Pools zum Abkühlen. 😀
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.
Die Aufgaben nannten sich Reislager (Rice Hub (EN)), Tropischer Garten (Tropical Garden (EN)) und Rennen (Race (EN)). (Nach Schwierigkeit sortiert)
Beim Reislager ging es darum, den besten Ort für ein zentrales Reislager zu finden, wobei alle Felder auf einer Linie sind. Die Aufgabe bestand darin, mit einem gegebenem Budget (also Anzahl der Längen der Wegstrecken zu den Feldern) einen Ort für ein Lager zu finden, zu dem möglichst viele Felder ihre Ernte verfrachten können. Die Lösung für das Problem war relativ einfach: das Lager muss auf einen Median.
Für alle, die das Problem per Hand lösen wollen, gibt es hier eine schöne Demo.
Im Tropischen Garten gibt es N Brunnen und M Wege, wobei jeder Weg 2 Brunnen verbindet. Der Botaniker wählt immer den schönsten Weg, wenn er bei einem Brunnen angelangt ist. Seine Gruppe will aber nach K Wegen bei Brunnen P sein. Zu Berechnen sind die Anzahl der möglichen Wege für jede Gruppe. Auch für den tropischen Garten gibt es eine Demo.
Als das schwierigste Problem am ersten Tag galt das Rennen. Gegeben ist wieder ein Baum (mit N Städten und N-1 Autobahnen). Gesucht ist eine Strecke zwischen 2 verschiedenen Städten mit gegebener Länge. Divide & Conquer ist die optimale Lösung für dieses Problem.
Zweiter Tag
Die Aufgaben des 2. Tages sind Tanzende Elephanten (Dancing Elephants (EN)), Auf der Flucht vor dem Krokodil (Crocodile’s Underground City (EN)) und Papgeien (Parrots (EN)). (Nach Schwierigkeit sortiert). Am zweiten Tag konnte nur noch Gennady Korotkevich die volle Punktezahl erreichen.
Tanzende Elephanten nannte sich ein Beispiel, bei dem sich auf einer Bühne eine Anzahl an Elephanten bewegt und Kameras sollen diese fotographieren. Leider reicht oft nicht nur eine Kamera aus, um alle Elephanten fotografieren zu können. Deshalb ist die minimale Anzahl an Kameras gesucht, die benötigt werden. Um diese Aufgabe zu erschweren, tanzen die Elephanten ständig, also es ändern sich ihre Positionen.
Wer will kann auch hier die Demo probieren.
In einem Labyrinth gefangen und auf der Flucht vor dem Krokodil, das immer einen Weg versperrt ist eine Archäologin. Aufgabe des Programmierers ist es, die kürzeste Zeit zu berechnen, die die Archäologin braucht um sicher einen Ausgang zu erreichen. Dabei sind die Wege zwischen den Räumen unterschiedlich lang und das Krokodil, das nach jedem Schritt seine Position ändern kann, kann das Durchlaufen eines Ganges verhindern.
Demo
Bei den Papageien handelt es sich um eine nachrichtentechnische Aufgabe. Dabei ist eine Sequenz von Zahlen so zu versenden, sodass danach nicht nur die ursprüngliche Nachricht wiederhergestellt werden kann, sondern auch die Reihenfolge, denn die kann sich beim Senden ändern! Noch schwieriger wird es beim letzten Subtask: Hier ist zusätzlich noch eine starke Komprimierung nötig. Die für alle Punkte nötige Komprimierung konnten nur mehr 6 Teilnehmer implementieren.
Ergebnisse
v.l.n.r: Aaron Montag, Tobias Lenz, Johannes Bader und Patrick Klitzke
Das deutsche Team konnte gleich mit 3 Medaillen zurückkehren: Silber ging an Tobias Lenz aus Niederkassel bei Bonn, Bronze an Aaron Montag aus Baindlkirch bei Augsburg und Johannes Bader aus Calw. Patrick Klitzke ging leider leer aus. Von den Vieren darf Tobias Lenz nächstes Jahr noch einmal teilnehmen.
Im österreichischen Team, bestehend aus Fabian Hammerle (Stiftsgymnasium Admont), Markus Hasenöhrl (HTL Braunau), Thomas Tangl (HTL Pinkafeld) und Sebastian Wagner (BRG Amstetten), konnte niemand eine genügend hohe Punktezahl erreichen. Markus Hasenöhrl verpasste um wenige Punkte eine Bronzemedaille.
Nikola Djokic (Kantonsschule Alpenquai, LU) aus der Schweizer Mannschaft verpasste zwar knapp eine Goldene, freut sich aber auch über seine silberne Medaille. Mit dabei waren noch Lazar Todorovic aus Stäfa (Realgymnasium Rämibühl, ZH), Cyril Frei aus Tägerig (Kantonsschule Baden, AG) und Stefan Lippuner aus Trin (Bündner Kantonsschule, GR)
Links
- IOInformatics – Offizielle Website der IOI
- IOI2011
- IOI2011: Aufgaben
- IOI2011: Ergebnisse
- IOI2011: Videos
- IOI2011: Fotos
- Blog der deutschen IOI-Mannschaft
- Blog der schweizer IOI-Mannschaft
IOI 2012
Die 24. IOI wird in Sirmione am Gardasee in Italien statt finden, in der letzten Septemberwoche. Mehr von meinem Insider-Wissen will ich noch nicht verraten 😉
Fußnoten
1Außer dem Land, das wegen Schummelversuchs für 10 Jahre gesperrt wurde: Nordkorea
2Auf der Website wird zwar eine Altersbegrenzung genannt, ist aber meiner Meinung nicht ernst zu nehmen!
3Nur etwa 40 Länder sandten Besucher zur IOI
4alle Zeit = 23 Jahre
Kommentare (5)