ACM ICPC 2014 World Finals

2014FinalsRollerThis June I was privileged to be able to accompany University of Cambridge team to ACM ICPC 2014 World Finals in Ekaterinburg, Russia. So, I present you with a brief recollection of the event.


First of all, let me explain what this event is all about. ACM ICPC is short for Association for Computing Machinery International Collegiate Programming Contest and it is the algorithmic programming competition for University students in the world. It begins in the autumn with regional competitions all around the world. This year’s edition saw 32043 contestants from 2286 universities in 94 countries competing for glory. By the time the World Finals kicks in in late spring/early summer, only 122 universities are left and only a single team per university is allowed at the final stage.

So, what exactly competitors do in ICPC? Glad you asked. This is the team competition, where every team consists of 3 University students and they get to solve a number (usually 12 at the World Finals) tasks in 5 hours using a single PC. For every task there is no partial score – you either got it right (meaning that you got the correct answer in specified time and memory limits for every single test case the organizers have) or you don’t. Whatever the verdict, it gets immediately delivered to the team. For every problem solved you also get the balloon delivered to you (hence the amount of balloons in the photos).

ACM ICPC Trophy

ACM ICPC Trophy

After 5 hours have passed, all teams are ranked according to the amount of problems they solved. To determine the medals, the top teams are also ranked according to tiebreaker if the amount of tasks solved is exactly the same – the sum of times it took the team to solve every accepted problem (with extra 20 minutes for every incorrect submission on accepted problem). Then first four teams receive gold medals, next four teams get silver with the next four teams collecting bronze medals. Few extra awards such as continental champions and fastest solution on every problems are also given. And of course, world champions receive the coveted title and the trophy displayed on the right.


So, it all started back in Michaelmas, when I volunteered to organize the selection stage at Cambridge and managed to convince Dr Andrew Rice that it is a good idea for him to be a coach of Cambridge teams. With a help of many people we have successfully held the selection stage and out of the field of 10 teams selected 3 to participate in the ACM ICPC NWERC 2013. Yey, more unknown abbreviations! You should be familiar with the first two, the third one stands for Northwestern Europe Regional Contest. This is essentially one of the semifinals for ICPC where teams from Belgium, Germany, Denmark, Finland, United Kingdom, Ireland, Iceland, Luxembourg, Netherlands, Norway and Sweden compete for just 3 spots in the World Finals. Cambridge performed really well there, taking 2nd, 4th and 5th places, bringing home 2 gold and 1 silver medals (available for display at Dr Rice’s office) and the ability to send the best placed team to the World Finals. As such, team Beuler advanced to World Finals. Unfortunately, Dr Rice was unable to join us there, so our delegation consisted of four people, displayed in the team photo below (triposes are stated for the last academic year):

Beuler

University of Cambridge: Beuler
Boris Grubic, Contestant, Trinity College, Computer Science, Part IB
Bogdan-Cristian Tătăroiu, Contestant, Churchill College, Computer Science, Part II
Eduard Kalinicenko, On-site Coach, Queens’ College, Computer Science, Part IB
Domagoj Cevid, Contestant, Trinity College, Mathematics, Part IA
Andrew Rice, Coach, Queens’ College, Computer Science, Director of Studies
Photo by Bob Smith


So, with introduction out of the way, let me get to the event itself. It usually happens over the course of 4 days. The first day is the registration day. This is when most of the teams arrive in the hotels, and then register for the event, which includes taking a providing personal information, receiving various stuff, along with the coveted T-Shirts and taking a team photo. But first, one has to arrive. We departed from 4 different cities, but all met in Moscow’s Sheremetyevo early in the morning for the final flight to Ekaterinburg, arriving there at 2pm. Of course we were immediately greeted by guides and buses, which would take us to the hotel. This year the delegations were spread across 8 different hotels in Ekaterinburg. There were regular buses travelling between them at mornings and evenings though, so it wasn’t a big of a problem, and even if you miss a bus, the walking distance was rather reasonable.

ICPC

ICPC T-Shirts, ready to be collected
Photo by Maddy Wang Renström

So, after arriving in our hotel and registering there (luckily, hotels register you themselves, so you don’t need to do paperwork to get out of Russia without problems yourself), we received backpacks from Ural Federal University (UrFU, for short) with some nice stuff, like local SIM cards, mp3 player, USB hub or dice, which was intended to help you make the decisions during the contest. Our registration slot was at 8:30pm, but the organizers thought it would be a good idea to get us there as early as possible (which was a common theme throughout the whole event), so we arrived there with obviously nothing to do. Luckily, our team was multinational, which meant that Domagoj knew a team from University of Zagreb, Bogdan was in a similar situation with University of Bucharest. There was no team from Serbia, but Boris shared a lot of interests with Romanians, so it turned out fine as well. I wasn’t left out as well, as University of Latvia team was coming as well, with two of my teammates from two year ago. So, in the free time, some went out to explore the city, some went back to the hotel and I stayed there to monitor the situation and to meet some other people I knew. Then we managed to assemble ourselves for the registration and received our T-Shirts, handed in our team reference notebook, received a mascot of this ICPC – Urfoo, along with a lot of information sheets and booklets. Finally, after taking a team photo, we were able to get to our hotel to get some much needed sleep.


The sable Urfoo, mascot of ICPC 2014

The sable Urfoo, mascot of ICPC 2014
Photo by Rafał Sikorski

The second day was much more eventful. After a breakfast in the hotels, we were transported to attend the sponsored event (which one cannot skip without being disqualified), namely IBM TechTrek. In reality, it turned out to be pretty interesting event, where we were told a story of IBM Watson, the famous computer who won a game of Jeopardy! in 2011. The story didn’t stop there, as IBM saw the potential in the technology of cognitive computing and in early 2014 formed a business unit around it. After the speech, there was an interactive section where the audience could suggest the ways cognitive computing can be used in everyday world. At the end of the event, everyone had a chance to ask a question to the panel, which included creators of Watson and get Watson branded cap. After TechTrek, everyone had free time, except this time there were different events happening all over the place – like giant checkers, radio-controlled cars and the set of Angry Birds with actual slingshot. Also, everyone had a shot at creating graffiti by painting one of the 10 parts of it, after which they were put together and improved by professional graffiti artists. After that the Opening Ceremony of ICPC 2014 took place. It was about 2.5 hours long event, where the viewers were entertained by performances of various kinds, formal speeches and awarding some members of ICPC community for their contribution to the contest. Rather than describing the event in detail, let me direct you to a 2 minute video, summarizing the entire ceremony. Afterwards, the dinner occurred and on that the second day has ended.


The third day of ICPC is the day of the Dress Rehearsal. The most common reaction to that name is “What?”. Well, let me explain.

University of Cambridge team at the workstation Photo by Bob Smith

University of Cambridge team at the workstation
Photo by Bob Smith

The definition of the term, copied straight from Google, is “the final rehearsal of a live show, in which everything is done as it would be in a real performance”. No, this doesn’t mean that contestants get task statements a day in advance. This 2.5 hours practice session is not only for contestants, it’s for the organizers as well – and this is where they try to make sure that the next day, when the actual contest will happen, everything will run properly – system will be working, printouts will be delivered as fast as possible, balloons will be delivered etc. So, initially, no one else apart from the contestants are permitted on the floor. Later on, coaches are admitted from the audience stands to take pictures of the teams. Everyone else still has to be in the audience stands – the Dress Rehearsal is taken very seriously by organizers. No contestant is admitted without an ICPC T-Shirt (Too cold? Wear everything under the T-Shirt). In 2012 one poor guy forgot his badge in the hotel and had to drive back to collect it in quite an emergency. This year we were candidates for the same destiny, but luckily one of us only forgot a T-Shirt and hence I came very useful in eliminating the problem, since coaches are not required to wear a T-Shirt to dress rehearsal, so we were OK with an emergency T-Shirt swap.

But, the Dress Rehearsal is also meant for contestants to become familiar with the system. So, the contestants are usually given some practice tasks, which this year were actual ICPC World Finals problems from the past 2 years. Contestants can also ask questions or report problems (which we actually did on one occasion) and they are either answered immediately or if the immediate answer can’t be given or the question were deemed to be relevant to the whole field, it would be answered after the Dress Rehearsal and the lunch on the special half an hour session meant specifically for that purpose. After that, there weren’t really that many significant events anymore as the contestants were given time to rest. All coaches had a meeting with Bill Poucher, ACM ICPC Executive Director where some of the future development of ICPC was discussed. There was also a second practice session, which was optional (unlike 2 years ago), for contestants who needed more time to check out the system.

The panorama of the contest floor

The panorama of the contest floor

Which leads me to the final day of the ICPC – the contest day. These are the 5 hours some of the teams prepared for a year. Some of them – even more than that.

University of Cambridge team with the trophy Photo by Andrea Pereira de Almeida

University of Cambridge team with the trophy
Photo by Andrea Pereira de Almeida

But first, since everyone arrives early, Bill Poucher entertains the audience and gives everyone a chance to make a photo with the trophy. After that, the contestants are invited to the floor, while everyone else moves to the audience or stays in the hall, where live video coverage of the event is played. Yes, this event is very well covered, and to judge it for yourself you can view the entire coverage (or likely, parts of it). The live coverage contains various interviews, analysis of what is going on on the floor and also discussion of the tasks and their solutions (since contestants are quarantined anyway). There was also some innovations for the spectators – when the live coverage is available worldwide, this year there were an onsite exclusive feature – 10 workstations in the hall, where one can select a team and get a video (and possibly audio as well) from the webcam and the feed from the workstation, so that the coaches can track more precisely what his team is doing.

University of Cambridge team's feed in the middle of the contest

University of Cambridge team’s feed in the middle of the contest

As for the actual contest, this year’s tasks were considerably harder than the previous years. If you wish, you may take a look at them yourselves. If you really wish, you can even write the solutions for them and check them online. However, let me point to you to the easiest problems. Out of 122 teams, 96 have solved problem D, 66 have solved problem K and 55 – problem C. The next most solved problem, E, was solved only by 16 teams, which might hint at the level of difficulty. 4 out of 12 problems were left unsolved completely and no team solved more than 7 problems, including all-star team, who competed for fun in online mirror of the contest and consisted of Gennady Korotkevich (tourist), Petr Mitritchev (Petr) and Jakub Pachocki (meret), who all are currently in the world’s top 10 in algorithmic programming by two of the most popular ranking systems, with some occupying first places in them as well.

ICPC 2014 World Champions St. Petersburg State University

ICPC 2014 World Champions
St. Petersburg State University

Now, that I hopefully convinced you that the contest was really hard, after 5 hours of hard work, University of Cambridge has managed to solve 2 tasks, C and D, which turned out to be a respectable 45th place in the results. The team has tried to get a third problem, which would bring anyone to a very high 19th place, but, unfortunately, it was not to be, as we didn’t manage to get on a correct answer on either B or K. The detailed results are also available.

In the top though, the contest turned out to be very exciting. The scoreboard is always frozen in the last hour, so the team only knows their own verdicts – for everyone else the submissions are shown as pending and are later unfrozen at the closing ceremony. As it turned out afterwards, Moscow State University was in the lead for quite some time, until St. Petersburg SU leapt in front at 286th minute. The lead was not long lasted, as Moscow SU got it back at 290th minute by solving another problem from the 8th attempt. However it was not enough, as two minutes before the end, at 298th minute, St. Petersburg SU has managed to solve a problem from 9th attempt and took a championship by only 39 minutes advantage.

None of that was known in advance though (sort of, you can get some sort of idea from “exit-polls”, where teams ask one another for how many problems have they solved, but it’s never official), so we get exciting reveal of the scoreboard at the closing ceremony that happens almost immediately after the contest. To get some idea of what it looks like, here is a video for the scoreboard revelation (with actual presentations of awards cut out). Apart from the award ceremony itself, there are some speeches and performances as well, and also the next place to host ICPC World Finals is revealed, which in 2015 will be Morocco on May 16 – 21. After all of that, ICPC 2014 was officially closed and after a dinner to mark the occasion, some people began to go back to the hotels, and some stayed to attend the open-air disco party. I, though, headed for a tour around the city, and so I’ll leave you with a final panorama of Ekaterinburg. But before that I would like to say a huge thank you to the organizers of this World Finals for the wonderful event, Ural Federal University and volunteers from it for being an amazing hosts, Dr. Rice for all the help which made this possible and also University of Cambridge’s Faculty of Computer Science and Technology along with University of Cambridge’s Trinity College for providing financial support to cover the costs of the trip.

260

Advertisements