SOI Camp 2019

Sunday (10.02.2019, Elena Morbach)

Am Sonntag trafen wir uns um 12 Uhr beim HB Zürich, um eine Woche lang viel über das Programmieren zu erfahren und eine tolle Zeit zu haben. Dort trafen wir auch noch eine Delegation aus Israel und machten uns auf den Weg. In Luzern stiegen wir um und trafen dort noch mehr Leute und nahmen den nächsten Zug nach Sarnen. Dort stiess die slovakische Delegation hinzu und wir liefen zu unserer Unterkunft. Nach einer kurzen Einführung bezogen wir unsere Zimmer und trafen uns kurz später draussen. Dort spielten wir ein Spiel, um gegenseitig die Namen zu lernen, was sich als ziemlich schwer erwies. Nachdem die österreichische Delegation eintraf, gab es Käsespätzli zum Znacht. Als nach der ersten Runde noch viele hungrig waren, machten unsere Köche nochmals eine grosse Portion Pasta damit alle mit vollen Mägen, nach ein paar Runden Kartenspielen, schlafen gehen konnten.

Monday (11.02.2019, David Jenny)

In the morning, after eating breakfast, we were split into an advanced and a basic group, according to our experience and familiarity with coding. Of course, the participants that could go to the IOI last year were given extra lectures. That way everyone had lectures of challenging, but not impossible, difficulty. In the afternoon, after another lecture, a contest was held. That way, we, the participants, could practice to work under time pressure, which was actually quite fun. Nevertheless, the highlight of the day was the dessert;). This gave us the energy we needed to code late into the night (or play some card games).

Tuesday (12.02.2019, Alexandru Petrescu)

The day started quickly with the breakfast with its traditional bread with jams or Nutella and the milk with cereals. At 8 o’clock we’ve already started the warmup: the first problem asked us to turn a biconnected component into a strongly-connected one by directing the graph’s edges, a fine conclusion to the yesterday’s graphs main theme. In the second one we had to deal with advancing pointers on a circular array. In the end, Timon presented us the solutions.

Before the lectures begun, today’s main theme was announced: Dynamic Programming. In the standard track, we encountered problems involving optimal paths on grids and counting them, during André’s lecture. Then, Bibin taught us some combinatorial techniques and launched the following task: Given a tree, find how many topological orderings does it accept. Bibin mentioned that his lesson involved 3D knapsack and the students got a lot of confidence in implementing harder DP solutions. “They didn’t ask many questions, but they seem to have understood well”, Bibin said.

The advanced track started with Dor’s lecture. The lesson started with remembering some general facts of Dynamic Programming. Dor used both a Power Point presentation and the whiteboard to teach us how DP is used to solve tasks. “For the beginning, I showed two basic DP problems, one of which is less standard”. The lesson was pretty interactive, the participants were asking and answering questions and they had enough intellectual fun not to be bothered by the lack of breaks. “One of the students came to me and said the lesson was really great”, Dor mentioned. Then Daniel’s lecture followed. Next, Timon’s lecture was shorter due to a funny misunderstanding: Daniel to Timon: “How much time have I got left?” - Timon: “Minus 10 minutes”. Too bad Daniel understood only the suffix, and Timon had 20 minutes less to teach us some applications of the Knapsack problem.

In the IOI track, Misof gave us some very interesting problems. At first, a warmup counting problem that turned out to be another definition of Catalan Numbers. Then, a TopCoder challenge left us without ideas, until Misof gave us a hint that truly simplified the problem. After finishing it, he asked for a topic suggestion. The participants asked for… games! And they received games. After the introduction, we received an unusual problem that turned out to have a great generalization. For the end, Misof kept some pretty tasks that checked computational thinking and mathematical approaches rather than programming skills. He left us some homework: a fine constructive problem and 2 theoretical “gamey” questions.

The lunch has seen a premiere for this year’s camp: our excellent cooks prepared us meat! After enjoying it, we returned to the lectures and continued to learn about DP. The contest followed up, where the 42 participants had 4 problems to solve in 3h. Half of us managed to solve at least 2 of them, which means either we visibly improved from yesterday, or the set was more approachable. Perhaps both…

The solutions to the problems have been shown by the team leaders. All problems were either counting or optimization DPs. The hardest one also asked for the reconstruction of the solution, which turned out to have 2 ways to be solved for 100 points: Either through an algorithmical idea that amazed us, or through a “hack”, which was also used by participants to get high scores. This round has seen also a reevaluation with higher time limits, and the issues with the evaluation queue turned out to be minor during the contest.

We had a great dinner at which our heroes the cooks prepared us some fine rice in sauce with cheese. After each meal, the cleaning duties were successfully done by the responsible students of today. “Moving the stacks of plates really requires strength”, one of them mentioned.

Finally, we had 3 seminaries. Stephanie taught us how to prove for ourselves some greedy algorithm we come up with - including an easy solution for a problem in the yesterday contest. To sum it up, one approach is considering an optimal solution that differs from the greedily obtained one and show that one can change it to the greedy one without violating the restrictions and keeping the optimality. The other approach insisted on choosing the optimal solution that is somehow closest to the greedy one. In the end, she proposed a 2-players game that has a very strange property: One can prove the first to move can always win, but finding the right moves is really complicated. Another seminary was held by Benjamin, who talked about a program that checks whether your code really does what you wanted it to do, by logically reducing it to “true”, a process that involves checking for counter-examples automatically. Bibin talked to us in his seminary about providing correct proofs for the theoretical tasks.

To conclude with, the day proved to be most enlightening for all of us, thanks to the efforts of the team leaders and cooks who kept us well fed both intellectually and practically.

Wednesday (13.02.2019, Raphael Zumbrunn)

In contrast to our morning program of the previous days where we had had a warmup session after breakfast, we started the “no laptop day” with a longer teamwork session, where we solved theoretical tasks in our assigned groups. Goal of this was to prepare ourselves for the theoretical part of the second round. Each group consisted of four participants and the whole group had to solve 4 tasks which they had to present later. The difficult part was that everyone had to be able to present each problem later as we didn’t know who had to present what.

After enjoying a delicious vegetable lasagna, we were again put into groups, this time with a leader. In those groups we completed a scavenger hunt where at each point of interest we had to take the most creative picture that came to mind. We had a lot of fun walking around as it was something other than just sitting around and coding all day long. Refreshed we returned to solve a theoretical task similar to the ones found in 2T.

The funniest pictures that where taken on the afternoon were later presented accompanied by a lot of laughter. In the evening some of us played games in the main room while others tried to solve some more tasks to be even more prepared for round 2. A very popular game among a lot of SOI participants is a game called werewolves. A game which combines clever reasoning and a good intuition. The SOI camp offers a good balance between advancing your coding skills and enjoying yourself.

Thursday (14.02.2019, Jonas Meier)

In the morning, after breakfast, we had our usual warmup exercises. The main topic of the day was advanced queries. There was a quick introduction to the Segtree and then we discussed some very interesting problems that can be solved with queries. In the afternoon we held a contest which was a lot of fun. So far this camp was a lot of fun and I met a lot of interesting people. That is why we decided to ask some of the participants from other nations to teach us their language. We tried to speak Hebrew and had a lot of fun trying to pronounce Slovak sentences.

In the evening I attended a seminary about quantum computing which was extremely interesting and completely new to me. Afterward, we played some games and tried to implement some of the new topics we learned about. All in all, it was quite a challenging and very enlightening day. A big thanks to all the leaders who make this possible and greetings to our new international friends :)

Friday (15.02.2019, Dario Ackermann)

Unser Tag startete wiederum mit Frühstück. Einige Teilnehmer hatten sich in den letzten Tagen und Nächten so ins Zeug gelegt, dass sie heute kaum aus dem Bett kamen. Schlussendlich jedoch haben es alle geschafft – der letzte, finale und wichtigste Contest, liebevoll «Egg-Cup» genannt, startete pünktlich um 8 Uhr. Während 5 Stunden hatten alle Teilnehmerinnen und Teilnehmer des Lagers Zeit, um Aufgaben zu lösen, in denen es unter anderem darum ging, einen optimalen Plan für einen Portier eines Hotels zu erstellen, zu berechnen, wie viel Pasta eine Maus mit verschiedenem Gemüse kochen kann und auch, eine verlorengegangene Zahlenfolge mit Vergleichsoperatoren wiederherzustellen. Nach 5 Stunden des Programmierens, Debuggens und harter verrichteter Arbeit standen die Sieger des Egg-Cups fest.

Um 13.00 gab es dann – endlich – Essen. Trotz grösster Bemühungen schaffte es das Küchenteam nicht im ersten Anlauf, die hungrigen Programmierer mit Älplermaggronen zu füttern – deshalb gab es für diejenigen, die immer noch Hunger hatten, Pasta. Um 15.00 Uhr folgte dann eine Vorstellung der optimalen Lösungen für den Contest (und damit verbunden, Facepalms, wenn der Lösungsansatz trivial gewesen wäre). Danach hatten wir freie Zeit, welche einige von uns am See verbrachten. Pünktlich zum Nachtessen standen wir dann aber alle wieder auf der Matte. Nach dem Essen war die Rangverkündigung des Cups. Es folgte ein Lagerabend wie jeder andere – Karten- und Brettspiele bis in die frühen Morgenstunden, während einige von uns sich noch entschieden, einen Nachtspaziergang zu unternehmen. Wenige Teilnehmer nahmen noch am Gamejam, dem Entwickeln eines (einfachen) Spiels zu einem bestimmten Thema bei. Sie beendeten ihre Arbeit um 06.15 Uhr morgens und konnten noch knapp eine Stunde Schlaf bis zum Morgenessen geniessen…

Saturday (16.02.2019, Benjamin Schmid)

The last day of the camp was dedicated to cleaning our house. After only working with the mind this was a welcome change and as such, the cleaning progressed quite fast. We were already done at 11:30 and so the participants could take the train back home almost two hours earlier than planned. And with this another successful SOI Camp came to a close. Thank you to everyone who participated and who helped organize the camp. Especially a large thanks goes to the kitchen team who worked day and night to provide us with delicious food.

All the best to all participants in the further rounds of SOI.