Flimscamp

In Flims trainiert eine Delegation der SOI zusammen mit einer Gastdelegation aus Hong Kong eine Woche lang für die Internationale Informatikolympiade.

Timon Stampfli
News

Um für die IOI zu trainieren geht eine Schweizer Delegation gemeinsam mit einer Gastdelegation aus Hong Kong für eine Woche nach Flims. Vom 2018-07-15 bis 2018-07-22 üben die Teilnehmer Aufgaben zu lösen, wandern in der Umgebung und geniessen das gute Essen.

Jeder Schweizer Teilnehmer verfasst zu einem Tag einen Bericht.

Sunday, July 15th (Simon)

It’s the first day of the Flims camp! We are all very excited about it. We gathered at Zurich HB at 10:15, and we took the train and the postbus to Flims. At around 12:30, we arrived in Flims. Our hotel was called Arena Lodge, it’s a very nice place with outdoor cafeteria where you can see the beautiful mountains around Flims. In Coop, we bought bread, drink, cheese and sausages as lunch and we brought them back to the cafeteria to eat. After lunch the Hong Kong team also arrived at the hotel. We gathered together and introduced ourselves to each other. After that I also went out with the Hong Kong team to explore the city. In the evening everybody was invited to Erich Gebhardt’s home to have a grill party. It was really fun, the food was also delicious. Erich Gebhardt helped organize many things for the camp and was very friendly and nice.

Montag, 16. Juli (Julian)

Heute war der erste Trainingstag. Nach einem ausgiebigen Frühstück spazierten wir zur nahe gelegenen Schule, wo wir netterweise die Räumlichkeiten benutzen durften. Das Training begann sogleich mit einer Einführung in “Fenwick-Trees” von Martin, was eine Art der Datenspeicherung ist, welche schnelle Veränderungen und Berechnungen ermöglicht. Um halb eins war dann das Mittagessen angesagt, welches die Leiter für uns in der Schulküche zubereiteten.

Nachmittags stellten die Teilnehmer aus Hong Kong uns noch einige Aufgaben sowie eine sehr spezifische Methode vor, um gewisse Tasks schneller lösen zu können (das sogenannte CDQ D&Q). Dies ist eigentlich eine Erweiterung einer bekannten Strategie: Divide & Conquer (zu Deutsch Teile und Herrsche) wird auch an der SOI häufig gebraucht. Trotzdem kannten selbst die Leiter aus der Schweiz die vorgestellte Technik noch nicht.

Danach bekamen wir dann einige Aufgaben, welche mit Hilfe der Fenwick-Trees gelöst werden können. Allerdings ignorierten gewisse Teilnehmer das Gelernte einfach und implementierten die Probleme auf eine andere Weise…

Am Abend assen wir nochmals in der Schule, bevor der offizielle Teil vom Montag vorüber war und wir noch etwas Freizeit hatten.

Dienstag, 17. Juli (Bibin)

Wie jeden Morgen standen wir auf, assen Frühstück und gingen los. Diesmal aber nicht zur Schule, sondern zum “Galaaxy”. Auf dem Weg dorthin verbrachten wir unsere Zeit mit gegenseitigem Rätselstellen: Wie würden demokratische Piraten ihr Gold aufteilen oder wie kann man dafür sorgen, dass von abzählbar unendlich vielen Gefangenen mit schwarzen oder weissen Hüten nur endlich viele sterben. Jedoch waren einige Rätsel bereits bekannt, oder wurden schnell gelöst, also versuchten wir ein eigenes Rätsel zu stellen: Welche Strategie ist die beste, wenn man überabzählbar viele Gefangene mit schwarz oder weissen Hüten hat, die nur nach vorne schauen können, und in einer zufälligen Reihenfolge ihren Hut erraten müssen?

So vertrieben wir uns die Zeit im Bus und in der Gondel, bis wir dann auf 2252 Meter über Meer Galaaxy betreten durften. Das Gefühl innen war futuristisch und doch Retro, denn es standen Aliens herum, Bilder von Astronauten, Regale gefüllt mit Büchern und Spielzeugen, aber auch Retrogegenstände wie Röhrenbildschirme. Dann wurde uns die “Bridge” vorgestellt. Wenn ich es zusammenfassen müsste: ein Luxusarbeitsplatz. Es war ein riesiger runder Raum, überall standen Tische mit verschiedenen Stühlen da und von der Decke hingen Steckdosen zum runterziehen. Auch gab es einige Whiteboards und ein Zimmer aus Glas für Meetings. In der Mitte war eine runde Lounge mit Kamin in der Mitte. Die Dekoration fühlte sich gemütlich, aber doch extravagant an. Und natürlich gab es um das Zimmer grosse Fenster um die Aussicht zu geniessen.

Das Programm war, am Morgen zu Wandern, mittags in der Galaaxy Bar zu essen und am Nachmittag in der Bridge einen Contest durchzuführen. Jeder konnte selber entscheiden, wo man hinwandern wollte, solange man rechtzeitig zurück ist. Remo und ich sahen einen kleinen Felsberg und setzten uns das Ziel diesen zu erklimmen. Von oben hatten wir einen schönen Überblick über das Gebiet und sahen von dort aus unser nächstes Ziel: Die Messing Kugel von Peter Trachsel. Also huschten wir hinunter und sahen uns dieses Kunstwerk an. Es hatte etwas Spezielles an sich, dass ein geometrisches Objekt mitten in der Landschaft steht.

Nachdem wir zu Mittag gegessen hatten, startete der Contest. Wir hatten drei Aufgaben und 3 Stunden Zeit. Bei einer Aufgabe mussten wir den kürzesten Weg durch die Stadt finden, wobei wir jedoch an Bikesharing Stationen ein Velo ausleihen und zurückgeben durften. Bei der nächsten Aufgabe waren drei Schoggirezepte gegeben und man musste die Anzahl Rezepte zählen, die zu allen drei gleich anders war. “Anders” definiert als die Anzahl Zutaten, die es zusätzlich hatte, oder fehlten. Bei der letzten Aufgabe hatten sich Geheimagenten in einer Linie aufgestellt. Jeder Agent hat eine andere Position und Renngeschwindigkeit. Nun wollte man herausfinden, welcher Agent bzw. Agenten zuerst am UFO ankommen würden, wenn es auf einer bestimmten Position auf dieser Linie landen würde.

Nach dem Contest gingen wir wieder zurück ins Hotel, wobei auf der Rückreise eine Diskussion entstand, wie man ein Laufband auf einer schiefen Ebene kontrollieren würde um einen Skateboarder in der Mitte zu halten.

Zurück angekommen gab es eine Diskussion über langsame Sortierverfahren. Unser Ziel war es, einen Algorithmus zu finden, der im Worst Case terminiert und eine möglichst schlechte asymptotische Laufzeit hat. Ausserdem sollte es in jedem Schritt etwas tun, das einen näher zur Lösung bringt. Eine Idee von Nicolas: Man generiert alle Permutationen. Um nun herauszufinden, welches dieser Permutationen sortiert ist, sortiert man diese Listen von Permutationen mit dem gleichen Algorithmus. Dies tut man solange wie man möchte und findet am Schluss mit einem Bubblesort heraus, welches wirklich das Minimum ist. Die Laufzeit wäre O((n!!!…!!)2).

Zum Znacht assen wir in der Pizzeria Vorab. Hier kamen natürlich wieder interessante Fragen auf: “Was ist ein Judy Array?”, “Kann man 5dl Eistee mit einem 3dl und 1.5dl Glas zur Hälfte teilen?” und “Wieso dreht sich ein Glas im Uhrzeigersinn, wenn man es im Gegenurzeigersinn dreht?”.

Wieder beim Hotel angekommen gab es noch ein paar Runden “One Night Werwölfeln”. Für die, die das Spiel kennen, einige lustige Konfigurationen: einmal gab es vier Freimaurer, ein anderes Mal haben drei Leute behauptet den Insomniac gewechselt zu haben, aber dieser bestreitet es und Johannes war als Gerber immer zu glaubwürdig, sodass er nie verdächtigt wurde. Am Schluss diskutierte Remo mit mir, wie man die Gewinnstrategie in diesem Spiel herausfinden würde, bevor wir dann zu Bett gingen.

Mittwoch, 18. Juli (Tobias)

Nach einem weiteren Morgenessen ging es heute wieder in die nahe gelegene Schule. Die Lösungen zu den Aufgaben des gestrigen Contests wurden vorgestellt und besprochen, dazu wurde einige mit diesen Aufgaben verbundene Theorie behandelt. Danach konnten wir mit dem neuen Wissen nochmals versuchen, die Aufgaben zu lösen, was auch den meisten gut gelang.

Nach dem Mittagessen gingen wir zum Caumasee. Dieser hat eine wunderschöne Lage in einer Senke umrundet von Wald. Von Volleyball bis zu Sonnenbaden gab es zahlreiche Möglichkeiten und trotz eher tiefen Wassertemperaturen wagten sich viele in den See, einige schwammen sogar bis zu einer Insel in der Mitte des Gewässers.

Am Abend durften wir Capuns, ein traditionelles Bündner Gericht, ausprobieren. Es handelt sich dabei um mit Kräutern und Salsiz angereichertem Spätzleteig, welcher in Mangoldblätter eingewickelt wurde. Dazu gibt es eine Sauce aus Milch und Bouillon. Danach ging es wieder zurück ins Hotel, wo wir wieder etwas freie Zeit hatten.

Donnerstag, 19. Juli (Nicolas)

Mein Bericht fängt mittwochabends um ca. 22:30 Uhr an. Da der Wetterbericht eine sternenklare Nacht vorausgesagt hatte, entschied ich mich ein nochmals zum Caumasee zu begeben, um die Milchstrasse zu fotografieren. Währen den folgenden drei Stunden wanderte ich zum See, probierte verschiedene Perspektiven aus, stand (aus versehen) mit beiden Füssen ins Wasser und wanderte zum Hotel zurück.

Mehr oder weniger ausgeschlafen assen wir Frühstück. Die Vorlesung am Morgen handelte von DP (dynamic programming) Optimierung mit der Vierecksungleichung. Die Vierecksungleichung besagt, dass in jedem Viereck die Summe der Diagonalenlängen immer grösser als der halbe Umfang ist. Nachdem Daniel uns die nötige Theorie beigebracht hatte, konnten wir das Gelernte an zwei Aufgaben festigen.

Kurz nach 12 Uhr gab es Fajitas mit Glacé als Dessert. Da ich aber schon von meinem Götti zum z’Mittag eingeladen war, gab es für mich im Restaurant Haldenhaus ein leckeres Schnipo.

Das Nachmittagsprogramm wurde von Stefanie geleitet. Sie gab uns drei verschiedene IOI-Aufgeben die wir lösen versuchen sollten. Bei einer der drei Aufgaben mussten wir Aman helfen, während der Eröffnungszeremonie der IOI 2015 möglichst effizient Geschenke an die Teilnehmer zu verteilen. Anschliessend hatten wir noch ein bisschen Freizeit.

Kurz nach sechs Uhr liefen wir gemeinsam zum Fidazerhof, wo wir zum Essen eingeladen waren. Nachdem wir alle freundlich begrüsst wurden, wurde uns eine leckere Kürbissuppe als Vorspeise serviert. Das Hauptgericht war ein leckeres Stück Fleisch mit Spätzle als Beilage. Zwischendurch diskutierten wir über viele verschiedene Themen, darunter auch, ob das Lambda Zeichen im NixOS Logo von Haskell gestohlen wurde oder nicht. Zum Schluss gab es noch ein leckeres Schokomousse.

Als alle wieder zurück im Hotel waren, spielten wir noch ein paar Runden Werwolf, programmierten und genossen den Abend.