Jaakko Kurhila, Head of Studies
The worl-wide finals for the annual ACM International Collegiate Programming Contest (ICPC) for students were held last Friday, the 5th February 2010. This year, they were held in Harbin in north-east China. A total of 103 three-member teams had been sifted to the finals through numerous trial contests throughout the world among students at the BSc and MSc level. There were some 22,000 participants in the preliminaries, and they represented 1,931 universities in 82 different countries. The CS Department’s team, Aleksi Hartikainen, Mika Laitinen, and Mikko Sysikaski, gained a respectable 36th place in the finals.
The standard of the contest was very high, and the problems especially challenging this year. The CS Department’s team managed to solve four of the ten problems in five hours, while there were many teams that were not able to solve a single problem during the finals. The winning team from Shanghai Jiaotong University solved 7 problems in the time given.
Young heroes: Mikko Sysikaski, Mika Laitinen and Aleksi Hartikainen
For many years, Russia and the Asian countries have dominated the contest, and this did not change this year, either, as the top three teams in the finals came from Shanghai Jaiotong, Moscow State University, and National Taiwan University. Of the three universities that went on from the European preliminaries, KTH of Stockholm came 12th and the German Friedrich-Alexander University came 36th. Of high-end universities known for their prowess in computer science, the ones to reach the finals were Stanford (14th place), Cornell (14th), Carnegie Mellon (14th), MIT (14th), Univ. Illinois Urbana-Champaign (honorable mention, one problem solved), and Univ. Texas Austin (honorable mention, no problems solved). Petrozavodsk State University, well known to many of the Department’s employees, did very well this year with their 5th place.
Finland has barely considered the significance or PR value of the AMC ICPC contest. Many of the university teams had a large team of supporters along, in addition to the coach and assistant coach. The Rector of Petrozavodsk followed along with his university’s team the whole week. Petrozavodsk also organises an open training camp in preparation for ICPC twice a year. The level of skills among the participants is illustrated by the fact that the main sponsor, IBM, promised to offer the members of the four top teams positions at IBM, and traineeships around the world for the other 100 teams. The director of the contest, William B. Poucher, mentioned at the coaches’ meeting that the President of Russia had shown his respect to last year’s winning team (St. Petersburg State University of IT, Mechanics and Optics) by inviting the whole team to his summer house to celebrate their victory.
The Chinese public TV company, CCTV, showed a one-hour compilation of the contest, and the local Harbin TV a 3.5-hour broadcast. The whole contest, including award presentations and introductions, was filmed with 10 TV cameras and broadcast live for 7.5 hours. The contest judges analysed the problem solutions and their pitfalls during the live broadcast. The screen of each team was also fitted with a camera and microphone, so their work could be shown on TV. The judges were also able to follow each screen. This meant that the broadcast from the technical support enabled the judges to comment on each team’s attempts at solving the problems in real time; the team from Waterloo University, for example, made the mistake in one of the problems of treating a floating-point number as an integer. The viewers could follow as they hunted for the bug; it was found at last but they wasted a lot of time (placing 14th)
In the ICPC contest, the three-member teams solve programming problems that are checked by computer (and by hand). They have 5 hours and ten problems to solve. Even the easiest problems in the contest exceed the requirements for the Data Structures Project at our department, and the harder ones require the kind of knowledge and skills taught at the course Algorithms Design and Analysis, such as dynamic programming. Instead of the user interface, the focus in the problems is on algorithmic solutions, so in- and outputs are made as straightforward as possible. All the problems of the ICPC finals are available on paper in the break room for anyone who likes this kind of brain teaser. As a matter of interest, the Shanghai Jiaotong University that won the contest solved four problems (C, D, G, J) in a little over an hour; the first problem was solved in 25 minutes (Belorussian State University solved problem J). In this contest, in principle the code must also be tested since the teams are given a 20-minute penalty for each failed solution, which may affect their placement significantly.
Competitive programming is a real art that you cannot help marvelling at. It is obvious that you need a huge amount of work to develop such artistry. The team from the Department of Computer Science consists entirely of second-year students. They have time and every chance of improving, but to date their achievements have already been brilliant. It has been a privilege to go along with the team. Their journey continues towards new challenges. Next academic year, the Nordic NCPC preliminaries will be held in October, the north-western European NWERC preliminaries in November in Bremen, and the ICPC finals in Cairo in March 2011.