CEOI 2016 in Romania

Freitag, 15. Juli

Am ersten Tag unserer Reise nach Rumänien haben wir uns am Morgen um neun Uhr am Flughafen Zürich getroffen. Von dort sind wir mit dem Flugzeug über Wien bis nach Iași geflogen, wo wir drei Tage verbringen werden. Nachdem wir unsere Zimmer im Hotel bezogen hatten, sind wir losgelaufen, um ein erstes Mal die Stadt anzuschauen. Später haben wir gegessen und sind am Abend noch in einen Escape-Room gegangen. Das ist ein Raum, in dem man als Gruppe eingeschlossen wird und dann eine Stunde Zeit hat, sich zu befreien. Um das zu tun muss man verschiedene Rätsel lösen und Codes für Schlösser finden. Die Rätsel waren ziemlich schwierig, doch es ist uns gelungen, kurz vor Ende der Stunde die Türe zu öffnen. Nach diesem Tag waren wir alle ziemlich müde und sind zurück ins Hotel gegangen.

Samedi, 16 juillet

Le matin du deuxième jour, nous sommes allés au Jardin Botanique de Iași. Nous avons pu observer de nombreuses sortes de roses dont beaucoup avaient des noms assez étranges ainsi que de nombreuses autres plantes. Après le repas, nous avons voulu visiter une église, mais nous n’avons trouvé qu’une chapelle du même nom mais qui n’était pas celle que nous voulions visiter. Nous avons profité de la suite de l’après-midi pour nous reposer avant de manger dans un restaurant français appelé Toujours. Après cela nous sommes finalement rentrés à l’hôtel pour dormir.

Sonntag, 17. Juli

Nach dem Frühstück machten wir uns auf den Weg für eine Wanderung. Wir nahmen einen Bus nach Păun, der schon ohne uns überfüllt war – eine ziemlich ungemütliche Fahrt. In Păun kamen wir beim Fernsehturm vorbei, unter dem viele Einheimische picknickten. Gegen Mittag wollten wir in ein Restaurant essen gehen, das auf der Karte eingezeichnet war, aber anscheinend existiert dieses Restaurant gar nicht. Stattdessen fanden wir einen kleinen Laden, in dem wir Getränke kauften. Wir setzten unsere Wanderung fort, und lösten verschiedene, schwierige Zwergenrätsel. Für die Heimfahrt nahmen wir wieder einen Bus, diesmal hatte jeder einen Sitzplatz. Zum Abschluss des Tages assen wir Pizza in einem italienischen Restaurant.

Montag, 18. Juli

Am Montag war unser letzter Tag in Iași. Eigentlich wollten wir noch ein Museum im Palast der Kultur besuchen gehen. Leider mussten wir aber feststellen, dass auch in Rumänien die Museen am Montag geschlossen haben. Um uns die Zeit zu vertreiben, haben wir im Park Tichu gespielt. Um halb fünf hat uns dann ein Bus in unserem Hotel abgeholt und in das ungefähr zwei Stunden entfernte Piatra Neamț gefahren, wo der Wettkampf stattfindet. Im Bus haben wir auch schon die meisten anderen Teilnehmer kennengelernt. In Piatra Neamț wurden wir von unseren Guides begrüsst und erhielten noch unsere T-Shirts.

Mardi, 19 juillet

Lors de notre deuxième jour à Iași, nous avons débuté la journée par un concours d’entraînement juste après le déjeuner. Ce concours était composé de quatre problèmes à résoudre en deux heures et demie. Nous avons ensuite dû prendre part à une session photo et après le repas, nous sommes montés en téléphérique sur une montagne près de Piatra Neamț de laquelle nous sommes ensuite descendus à pied. La journée s’est enfin terminée par la cérémonie d’ouverture officielle de la compétition.

Wednesday, July 20

Today was our first competition day. We got up early at around 7:30 AM, ate from the hotel lunch buffet and went on the bus at around 8:00 AM, with which we went to the competition site. We were presented to 3 tasks and had 5 hours to solve them, starting at 8:30 AM.

ICC was the only task that got fully solved by any of the contestants and involved the tracking of extraterrestrial road building on a planet with the name Mar Sara.

Kangaroo was the second task and involved a kangaroo jumping one-dimensionally across grass tiles. He has a starting position cf and a goal position cs and a range $\{1{\dots}N\}$ in which all grass tiles lie. Whenever he jumps on a grass tile he eats its contents and he must always switch between a jump to the left and to the right in order to avoid getting detected by hunters. How many possibilities are there for the kangaroo to visit every tile exactly once and land on the goal modulo 1000000007?

The third task was about inventing a card trick, where Dracula holds a pile of $2\cdot N+1$ cards, gives N to the first assistant and $N$ to the second assistant and takes one card for himself. The cards are numbered in increasing order from $0{\dots}N$ inclusive. The assistants can now each show 2 cards of theirs to the magician and if he can figure out what number Dracula holds he and his assistants are freed. Write a program for each of the assistant and one for the magician to solve this riddle. For more details about the tasks you can look at http://www.ceoi2016.ro/competition/online-contest/ and try to solve them yourselves.

Our team is happy with the results and especially Jan Schär scored very high and we are all very proud of him.

Afterwards we went on a bus trip to Cheile Bicazului, where we could roam around freely for 30 minutes, in which we decided to rent a boat and row along the lake. There were strunks of old trees in there so we had to pay attention to not get stuck on one of them.

We also walked through a large canyon and visited a dam at the lake Izvorul Muntelui.

The trip ended with a dinner in a traditional Romanian restaurant, where Ian danced to traditional music. The most exquisite and national dish probably was the Sarmale in a pot enclosed in bread and a miso-tasting sauce.

Donnerstag, 21. Juli

Heute haben wir einen Tagesausflug in die Stadt Iași gemacht. Dorthin mussten wir nach dem Frühstück erstmal 2.5 Stunden mit dem Bus fahren. Iași ist mit etwas mehr als $300\,000$ Einwohnern die viertgrösste Stadt Rumäniens – dementsprechend gab es dort auch noch einiges mehr zu sehen als in Piatra-Neamț selbst.

Als erstes haben wir den Kulturpalast besichtigt – ein altes, grosses Schloss, mitten im Herzen von Iași. Dort gab es neben einer Ausstellung über die Geschichte des Gebäudes und eine Austellung von Kunstwerken rumänischer Maler auch eine Ausstellung über rein mechanische Musikautomaten – von der Drehorgel bis zum Grammophon – inklusive Beschreibung und Vorführung ihrer Funktionsweise. Auch die Kathedrale Mitropolitană haben wir besichtigt.

Nach dem Mittagessen im Colegiul Sfântul Nicolae, einer kirchlichen Schule, hatten wir dann etwas Freizeit, die Stadt noch auf eigene Faust zu erkunden – für die meisten ging es dann aber einfach in die gigantische Schopping-Mall direkt neben dem Palast, um sich Souveniers zu kaufen und das ein oder andere Eis zu essen.

Freitag, 22. Juli

Friday was the second and last competition day. Again we had to solve three tasks in five hours starting at 8:30 AM. The first task was matching, where you had a string of characters in the range [a-z] and had to pair each character with another character of the same value. These pairs simulate two matching brackets, the left-one the opening bracket and the right-one the closing bracket. The task was to find the lexicographically smallest possible bracket matching for the input string, where N < 100’000. However they made a mistake and first wrote down a hard limit of N < 1’000’000 which is why the competition was extended for another 15 minutes. The intended optimal solution ran in O(N * sigma(N)) however an online contestant did submit a linear time solution so the mistake wasn’t that grave.

The second task was a funny one about grading submissions of contestants. The test-cases during the CEOI and similar conventions are usually grouped together. For each test-case you would then get a certain amount of points but only when you solved every test-case of the group correctly. Usually these test-cases are grouped before the contest but the objective of this task was to group the task yourself. We were given a number K, the exact number of groups one has to form from consequtive test-cases. This task only received partial feedback leaving the impression that they tried to minimize our points on this task.

The last task was an output only task where you had to create a graph connecting input nodes with output nodes over exactly one path with a limit of the sum of all indegrees and outdegrees.

After the contest we ate lunch and at the dining table we calculated our points and figured out that Jan Schär won a silver medal!

We swiftly had to find an official SOI t-shirt so Jan would shine on the podium in swiss colors and Jan also received a remote-controlled drone for his efforts. Every participant also received a CEOI mug, a traditional rumanian spoon, an egg cup, 2 CEOI t-shirts and a CEOI bag. The leaders also each received a traditional romanian spirit.

At night we played various card and board games with the german team hence they had to leave at 2 AM and on the next day we relaxed a bit until our airplane picked us up.