Daniel Graf – coding competition correspondent
Programming can also be a team sport. If you don’t believe me, you probably have not heard of the ACM ICPC yet. Besides the annual Turing award the Association for Computing Machinery also crowns the best student programming team each year in its International Collegiate Programming Contest [1]. Every year, more than 10’000 teams code in the regional contests across the globe to win one of the 120 spots in the world finals. And this year, our ETH VIS team qualified for these finals again!
Start locally, win globally
Each year in the fall, the ACM VIS committee organizes the ETH-wide selection contest together with polyprog from EPFL. So on Saturday, October 11, 27 students met for a day of solving puzzles and coding. If you took the ACM lab or the Algolab, you know the format: In five hours, you should solve and implement as many of the ten algorithmic problems as possible. Everyone on his own, no books, no internet. The things you learned in “Data Structures and Algorithms” in your first year are all you need to know. Most problems require you to take some well-known algorithm (breadth first search, Dijkstra’s shortest path, Graham scan, …) and use a clever twist to apply it to a new problem. You can code in C/C++ or Java and use their respective standard libraries as a starting point.
I had quite a rough start with a seemingly trivial problem buggying me right from the start. At some point I thought: Well this is it – no more world finals for me! It’s time to “retire”. But since the contest lasts for five hours, there was enough time to put this problem aside and try to catch up with the other tasks. There were some “practically inspired” tasks like: given the tree-structured street layout of a city with a point of interest (like a museum, beach or park) at each intersection, find the path between any intersection and the root (aka your hotel) that visits as many different attractions as possible. Another task that I liked was: given the “binary compatibility matrix” between N women and N men at a party, can you count the number of possible pairings between them, so that everyone has a dance partner? If you paid attention in your APC or Topics in Discrete Math course, you might remember the crucial idea for this task: the number of perfect matchings in a bipartite graph equals the permanent (“the determinant without the signs”) of its adjacency matrix. To compute it efficiently, some dynamic programming and some bittricks were required. Some other tasks were just directly mathematically phrased: given n points on a plane, how can you cluster them into two non-empty groups, so that the minimum distance between any pair of points in different clusters is as large as possible?
In the end, I was able to solve seven out of ten problems which resulted in the third place and I qualified for the first team of ETH together with Martin Raszyk and Andrei Parvu (both D-INFK). The second team was formed of Johannes Kapfhammer (D-MATH), Kieran Nirkko (D-INFK) and Luc Haller (D-MATH).
Training Day
With the teams selected, it was time to prepare for the next stage: the southwestern europe regional contest (SWERC [2]) that awaited us in Porto. As a team, we could only use a single computer now, so it was critical to communicate early and often: who should solve, code, debug which task? How to set the priorities? Who can print and code on paper? Also, for the next contest, we were allowed to bring a 25-page code book containing implementations of our favorite algorithms. That can help and means that you do not need to learn any min cost max flow algorithms by heart. We trained on some old contests to make sure that we were ready.
Olá Porto!
Leaving Zurich behind, we took off to Portugal or, more precisely, to the University of Porto where the contest was held. Unfortunately, our schedule for the weekend allowed sightseeing only during the night time, but we still got to see many nice spots in Porto, like the cathedral Sé do Porto or the old houses along riverside of the Douro. We met up with the two teams from EPFL for dinner and tasted some traditional food. I got a “Francesinha” which the in-flight magazine recommended as Porto’s specialty and turned out to be some toast- and cheese-wrapped steak soaked in some strange orange sauce – it was delicious! When I asked the waiter what the sauce was made of, he replied “beer, whiskey and many secret herbs that the cook won’t tell me – but you can use the Google to find them”. And so I did, but it is still a mystery to me…
Scratch the surface
Saturday started off with the official registration and two lectures. A professor from the University of Porto told us about the future of augmented reality driving supported by vehicular ad hoc networking. After that, a speaker from Microsoft talked about the difference between SaaS (Software as a Service) and PaaS (Platform as a Service) and they also announced that the winning team will get three Surface Pros.
“You can’t touch this!”
Then it was time for the dry run, a two-hour sample contest, made for us to get to know the procedures (“Do not touch anything until the contest starts!”) and for the judges to get a final load test of their grading system. It also gave us a first impression of our competitors and it looked like UPC1, the first team of the Universitat Politècnica de Catalunya in Barcelona, came well prepared and it might become a very tough race for the two spots for the World Finals. In total, there were 49 teams present representing universities from France, Spain, Italy, Portugal, Israel and Switzerland.
Seatless in Porto
The traditional “contest dinner” on Saturday night was held in a five star hotel this year, which resulted in a delicious buffet of Portuguese starters, dishes and sweets. Unfortunately, the budget was apparently not sufficient to provide chairs and so most of the 150 participants had a standing dinner. At least we left early this way and got a good night’s sleep before the big day.
Run, Jan! Run!
On Sunday morning we were finally ready to start coding for real. Unfortunately, Martin forgot to put on his mandatory white contestant T-shirt which we only noticed once we were already lined up to enter the contest floor. Facing the danger of disqualification, Jan, our coach, took one for the team and got a challenge of his own: run back to the hotel, fetch the shirt and get back within the twenty minutes left until the start of the contest. He managed to do it in fifteen – we were impressed! Dressed appropriately, Andrei got a good start, found a first doable problem quickly and got it accepted in the first hour. By that time Martin and I had found nice problems of our own and also got them accepted. But our competition did not sleep either and so after two hours, the UPC1 team had already solved five problems and also the first team from EPFL was ahead of us having solved four tasks.
99 Luftballons
One of the trademarks of the ACM contests are the colorful balloons that you get for solving a problem. Each problem has a different balloon color and so if you notice a sea of blue balloons around you, you should probably try to solve that task as well. But if you are among the top scoring teams this might not help too much. When I finished reading all ten tasks, I noticed that the overly-complicated story of the task “Playing with Geometry” was only trying to trick you into believing it were about non-trivial geometry when in fact all you needed to do was some coordinate-compression and polygon rotation and comparison. A special thanks at this point to Sandro Feuz, who lent us his mechanical keyboard for the weekend, which was a key strategic advantage. He also introduced me to the board game Ricochet Robot a few weeks before, which just happened to be used as one of the programming problems during the contest.
The sign of two
Cracking task after task, we managed to go into the final hour with seven tasks solved, which placed us right behind UPC1 and hopefully still in the world final ranks. Usually, the scoreboard gets frozen for the final hour but the contest system still showed us the ranking the entire time, so we always knew how tight it was. The first team from EPFL and the first team from Ecole Normale Supérieure Ulm both got very close to us, both solving their seventh problem in the final hour. Martin then managed to get our eighth problem accepted twenty minutes before the end and we desperately tried to fix one of the two remaining problems in the few minutes left. Ulm got an eight problem as well. But with 100 minutes more penalty time, we were safe and stayed on second place until the very end.
No Medal for you, come back one year
At the award ceremony we got the second gold medal and most importantly: a ticket to the world finals next May in Marrakech, Morocco. The second team of ETH did well too and reached place eleven of the final scoreboard [3]. We all expected the standard 4-4-4 medal distribution scheme, which would result in a bronze medal for them. Out of the blue, it was changed to 2-3-4 this year, leaving them empty handed.
But everyone in their team is still eligible next year, so they can all compete again in 2015. Well, unless some of you challenge them at the next local contest in fall! If you are interested in participating, take a look at the VIS ACM website [4]. It might be you travelling to Porto next November! In the nearer future, the helvetic coding contest will take place again at EPFL in March [5]!
Finally, I want to thank our two coaches Jan Wilken Dörrie and Robert Enderlein and all the volunteers of the ACM VIS commission that made the local contest and our participation possible.
Links
[1] http://icpc.baylor.edu
[2] http://swerc.eu
[3] http://swerc.up.pt/2014/reports/ranking.html
[4] http://acm.vis.ethz.ch
[5] http://hc2.ch