DANIEL GRAF – senior problem resolver
Why does ETH send three students to the African desert? Answer: So that they can spend five hours in front of a computer trying to solve as many problems as 127 other teams from all over the world. In other words: to the ACM International Collegiate Programming Contest World Finals in Marrakesh, Morocco [1].
“For the first time in ICPC history, a team at the world finals managed to solve all the problems!”, technical contest director John Clevenger announced at the closing ceremony. People started screaming and burst into standing ovations. The team from ITMO St. Petersburg, featuring coding legend Gennady Korotkevich, climbed the stage and was celebrated frenetically for solving 13 hard tasks in five hours. Everyone expected ‘tourist’ and his team to win, but that they would solve everything was still a big surprise.
But let’s rewind and let me tell you how we got there. After defending ETH’s colors at the finals last summer in Russia [2] and reaching second place at the Regional for Southwestern Europe in Portugal last fall [3], our team, consisting of Andrei Pârvu and Martin Raszyk and myself, qualified for what might be the most prestigious coding competition: the ACM ICPC World Finals. In case you don’t know how such a contest works, they are what inspired the exam formats of the courses ACM-Lab and Algolab at ETH. You get several algorithmic challenges and you have to find and implement an efficient algorithm for as many of them as possible. If you think you found a solution, you submit your code to an online grading system where it is compiled and run against different test cases. If you solve all of them correctly and fast enough, you get a point, otherwise you get some penalty time and can try again.
To prepare for these finals, our team met regularly to train on old problem sets. In April, we invited the teams from ITMO St. Petersburg (the aforementioned world champions) and the University of Wroclaw from Poland (who are currently all on exchange at EPFL and won the Helvetic Coding Contest [4] in March) for a training week at ETH. As expected, they crushed us every day, but it was still very valuable training. Petr Mitrichev, “the world’s second best programmer” according to Wikipedia, also joined us on Sunday. On his own, he solved way more problems than the three of us did. But in a field of 150 Russian teams we still got 27th place on that day, which made us optimistic for the tough contest that awaited us at the finals.
Before all the coding in Morocco, we also got to spend some time exploring Marrakesh. In the souks inside the walls of the Medina, hundreds of merchants wanted to test our bargaining skills, some of them successfully, I have to admit. We enjoyed lots of fresh orange juice on the Djemaa el Fna, the city’s main square. The town is full of hidden jewels, like the Jardin Majorelle, a garden donated by Yves Saint-Laurent, or the Quran school Medersa Ben Joussef, an architectural monument full of geometric patterns and decorations.
The contest itself took place in Palmeraie, a palm tree oasis in the outskirts of Marrakesh. We stayed at a great hotel. The pool-side breakfast contributed large parts to its greatness as it included cook-to-order omelets and blend-to-order smoothies. At one of these breakfasts, we also met Dr. Bill Poucher, the executive director of the ACM ICPC. He told us the story that a long time ago, ETH hosted the western European regional contest. There, the first north African team competed as a guest delegation. The year after, their coach started their own regional. That coach was now the host of the finals, and so Bill Poucher thanked us that the world finals could take place in Morocco this year – for the first time ever in the African and Arab world – as if it was only for ETH’s invitation. We only found out during the opening ceremony that he probably meant Ulm and not ETH. But it makes for a good story anyway.
The official contest took place under the high patronage of his majesty King Mohammed VI of Morocco, whose wife is a computer programmer by trade. There were 13 problems [5] given and we ended up solving five of them, roughly solving one every hour. Our team’s balance worked quite well: Everyone of us solved a problem on their own and then we heavily collaborated on the other two. One of the tasks even mentioned Switzerland: You are given a cuboid piece of Swiss cheese with several spherical holes in it (for each hole you get its center and radius). Where do you have to place parallel cutting planes to get S equi-voluminous slices?
The whole experience was quite intense. You are surrounded by huge projectors that show the live scoreboard and submission statistics. There were cameras everywhere and we were seated right next to the spectators area – yes, there are people watching you code from meters away. The contest was broadcasted on Youtube [6] and Twitch where thousands of viewers got to see live commentary on the tasks, their solutions and the progress of the teams. They could even show your screen as you were typing and had an entire team of analysts looking for your bugs.
Even though we were highly focused, the way we solved the last problem was quite funny.
Daniel: We should think about how to solve problem C?
Andrei: Oh, that’s the flow problem.
Daniel: Have you read it?
Andrei: No.
After thinking about it for quite a while:
Both of us: It is a min-cost matching, so we can use a flow.
So Andrei went ahead, implemented his favorite algorithm for finding a minimum cost maximum cardinality matching in a bipartite graph and got it accepted on first try. He wants me to note that the winning ITMO team needed two attempts 😉 – to be fair though: they solved it three hours before us.
At the end, a lot of teams solved somewhere between 3 and 7 problems. During the contest you get a balloon for every problem you solve. The color of the balloon indicates the problem. So after five hours the stadium was filled with balloons. During the last hour of the contest, the scoreboard is frozen. You still see who submits to which task but you don’t see whether it is correct or not. This is where ‘the resolver’ comes into play. The resolver is a neat visualization that maximizes the tension at the closing ceremony. It goes through the pending submissions one by one starting at the bottom of the scoreboard. This way, you can relive the final hour for all 128 teams and you can see how far up you managed to get. Our friends from Wroclaw got to place 14, very close to the medals, and ITMO won the championship ahead of Moscow State University and The University of Tokyo. Our rank 66 is nicely in the middle of the final scoreboard [7].
Without the support of the department of Computer Science and the chair of Professor Hromkovic, this trip would not have been possible. We would like to thank our coach, Jan Wilken Dörrie, as well as all the other members of the ACM VIS commission for all their efforts.
Now it is your turn to compete for ETH and beat the teams from France, Spain and Italy at the regional in Porto. The finals take place in Thailand next year! If you are interested, check out the website of the ACM VIS commission at http://acm.vis.ethz.ch/ for information about eligibility, training events, and the local selection contest which will take place early in the fall semester.
Links
[1] ACM ICPC World Finals: http://icpc.baylor.edu
[2] Report WF 2014: https://www.vis.ethz.ch/de/visionen/pdfs/2014/visionen_2014_5.pdf?end=44&start=40
[3] Report SWERC 2014: https://www.vis.ethz.ch/de/visionen/pdfs/2015/visionen_2015_1.pdf?end=40&start=34
[4] Helvetic Coding Contest 2015: http://hc2.ch
[5] Problem Set 2015: http://icpc.baylor.edu/worldfinals/problems/icpc2015.pdf
[6] ACM ICPC World Finals 2015 Live Stream: https://www.youtube.com/watch?v=xIvFJYo9928
[7] Final Scoreboard 2015: http://icpc.baylor.edu/worldfinals/results