Sunday, February 21, 2010

Asia trip, part 1: Bronze medal

As you may know, our team "!c[_]" from KTH qualified to the ACM ICPC World Finals 2010 in Harbin, China. ACM ICPC is a team programming contest and this year over 22 000 students from 1931 universities participated and 103 teams qualified to Harbin.

I slept only for half an hour in the plane, so when we arrived to Harbin, I got to bed in the hotel right away and woke up right before the registration and dinner. The next day we visited Snow Sculpture park and got a new coach. Fredrik was the technical director of the competition, so he could not be our coach. He found Roy from the Swedish Lund University, who was there as a director of Nordic Programming Contest, and I liked him from the very first moment. He came and told us "Give me 100 pushups each!". Chen and Ulf protested, so I had to make these pushups alone. Anyway, Fredrik didn't have time to train us, so we trained all by ourselves before the competition and we didn't feel like we lost a coach.

On Wednesday the Opening Ceremony was held and we had the first test contest afterwards. After the lunch we continued with building snow sculptures. Teams were supposed to build a long sentence together and our letter was N. My little finger was still affected by the frostbite accident, so I couldn't help even though I wanted. In the evening we went to the Ice World to see ice sculptures. It was great but my camera stopped working after a while in the -25 degree temperature.

Thursday was quite boring except the fact that we won the second practice session. But I have to mention that our definition of winning here is quite the opposite. The "first team in the practice session" is the team which solves all problems but has the biggest penalty time (in real contest you try to achieve the smallest penalty time, of course). I don't know how many teams use this definition, but at least we saw that Warsaw was aiming for big penalty time.

It's Friday, the day of the main competition. I slept well which is always important. When we finally got to our table in the contest arena, I felt that something was going on there. There was a lot of spectators, and photographers and TV cameras everywhere you look.

The start was very good. After about 2 hours we were on the 9th place with 4 solved problems. In the next two hours we were struggling with other tasks, but none of them was accepted. I went to the toilet a few times to get some fresh ideas but this didn't work as well as in NWERC 2009. In problem B we forgot to add just one line to make our 120-line solution work. My code was shown to the whole world in the webcast as an example of a long solution missing just one line. Finally, 30 minutes before the end, Ulf found the missing line. After 4 hours the scoreboard is frozen so you cannot see the actual results, which makes it more exciting.

In the last hour me and Chen were working on one problem each. 10 minutes before the end, mainly because of desperation, I decided to take a risk and send 4 similar solutions within 30 seconds. They only differed in one number. We were really surprised when one of them was accepted. As it turned out later, the solution ran 9.5 seconds and the time limit was 10 seconds. Our solution was probabilistic and the number I tweaked was the probability of running particular code. If I remember correctly, the correct probability was 1/6.

After the contest ended we were almost sure that 6 solved tasks should be enough for top 20. But of course we wanted top 12, because only top 12 teams get a medal (4 gold, 4 silver and 4 bronze). Chen and Ulf were sceptic about it, since we had big penalty time. Half an hour later, they showed the scoreboard and submitted solutions in the last hour of the contest. They started from the bottom to make it more exciting. After a while we were on 12th place, which means a medal, when only Stanford's submission could ruin all our hopes. It failed, so we got a medal! Even though I knew my frostbite-injured little finger would hurt like hell afterwards, I had to high-five with Ulf, Chen and Roy.

This year the competition was dominated by European and Asian universities. 8 European and 5 Asian universities made it to the top 13 (rant: they gave out 13 medals this year, because ACM ICPC likes to break their own rules). So we defeated all famous American computer science universities like Stanford, MIT, Cornell and Carnegie Mellon! My personal favourite Tsinghua University was only on 6th place, but another Chinese university took the first place  Shanghai Jiaotong University. But at least I got the second place right  Moscow State University.



KTH got a medal again after 4 years and now our school has all three medals. A lot of people congratulated us and a few news articles were written in Sweden. All three of us cannot compete any more, so it was a great ending of our ICPC careers. But after World Finals I became a coach of KTH, so now it's time to train teams which will hopefully qualify to the World Finals.

As usual, photos are on Picasa.

1 comment:

  1. congrutalations!!
    even it is not the first place, I pretty sure a lot of teams would like to be in place of your team. .
    personally, I think that it is a big achieve..

    grettings from Mexico. .

    ReplyDelete