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
Kommentare (5)