Nordic championships in programming 2014

The Nordic championships in programming (NCPC) and UK/Ireland championships (UKIEPC) 2014 took place last Saturday. For the second time I was the head of the jury together with Michał Pilipczuk from University of Bergen (now at Warsaw). This was one of my most memorable contests as a jury member, so I wanted to share some things that happened behind the scenes.

First some interesting facts about the contest.

• We had 257 teams in NCPC and 68 teams in UKIEPC. Most teams had 3 people, so we had almost 1000 people participating in 7 different countries!
• The jury could solve the whole contest (11 problems) in 463 lines of code. Something to brag about: 4 of the shortest solutions were mine.
• The winning team, Omogen Heap, solved all 11 problems 80 minutes before the end, when the second team only had 9 solved problems. These are the guys I have been coaching since high school and I have mentioned them in one of my previous posts.
• The hardest problem Basin City Surveillance had 33 solutions from the judges: 11 correct, 9 wrong and 13 slow ones. There were 76 test cases, most of them hand-crafted.

Now let me talk more about the hardest problem.

Basin City Surveillance

The problem: check if there is an independent set of size k in a bounded degree graph, where each vertex has at most 4 neighbors. See problem B here for the full problem statement. Initially, the upper limit on k was 11, which allowed 5^k algorithms to pass.

On the last Sunday before the contest, I sat down to write a random solution that seemed too simple to pass: it adds a random vertex into the independent set and erases its neighbors, and repeats this until there are no vertices left. If it fails to find k independent vertices, it restarts from the beginning with an empty set.

I was expecting such algorithm to require too many restarts, but only 100 restarts were enough to solve all the current test cases. I constructed some test cases that required 300 restarts, but my solution was still the fastest by far.

At about the same time, Per Austrin sent an e-mail suggesting that we raise the upper limit on k to 15, because he wrote a 3^k solution and thought the whole contest was too easy otherwise. Interesting! Per's and mine solutions were intriguing enough that falling asleep on Sunday took me too long.

Michał was against raising the limits at first, but at Monday lunch we decided to go for it to make the contest more interesting, even though there were only a few days left. The next couple of days we were all busy writing all kinds of solutions and test cases killing those solutions; that's why we had 76 test cases and 33 solutions. In the mean time, we also managed to prove that my random solution needs on average at most 3^k restarts.

Why the random solution needs only 3^k restarts?

First we need to prove a lemma that is important when you want to speed up the 5^k algorithm to 3^k. For a vertex u we have two options: either it is in some maximum independent set or it isn't. If it isn't, at least two of its neighbors are. One can prove this by contradiction. If only one neighbor v is in an optimal set, then we can substitute v for u and get an optimal solution with u in it – a contradiction. And if none of u's neighbors are in an optimal set and neither is u, then this can't be an optimal set: we could add u to it to make it larger. Again a contradiction.

Using this lemma one can write a 3^k backtracking algorithm, that either picks a particular vertex or two of its neighbors. With a little more insight this can be sped up to 2.31^k.

By the way, this been the first and probably the last time I have written a program with complexity 2.31^k. The slides contain the recurrence that leads tosuch complexity. If you want to be able to solve such recurrence, Concrete Mathematics is the recommended reading.

With some more work, the lemma above also implies that my random algorithm has 1/3^k chance of succeeding. The following proof is by Per Austrin. We call a vertex good if it is in some maximum independent set and bad otherwise. Let G be the fraction of good and B be the fraction of bad vertices, so we have G + B = 1. The claim is that there is at least one third of good vertices: G ≥ 1/3.

Let us count the number of edges L that connect good with bad vertices. By the lemma, a bad vertex has at least two good neighbors, so L ≥ 2Bn (n is the total number of vertices). We have a bounded degree graph, so each good vertex has at most 4 bad neighbors, 4Gn ≥ L. From these two observations, 4Gn ≥ 2Bn and 2G ≥ B. Since G + B = 1, G ≥ 1/3.

At each step my algorithm has 1/3 chance of picking a good vertex, so in total it has 1/3^k chance of succeeding. The average time complexity is therefore 3^k when an independent set of size k exists.

Omogen Heap's solution is also 3^k

Omogen Heap first submitted a slow 2ⁿ solution with a very small optimisation. In the next submission, they randomized their choices and added a cutoff: after 50 million iterations exit and print "impossible". They got accepted, solving everything 80 minutes before the end.

At first I thought the solution was too slow and our test data too weak, because I have overlooked the randomisation part. I told them that they got lucky. But with randomisation such solution actually has the same running time as my random algorithm, since the chance of stumbling upon a solution is high, 1/3^k.

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 only slept for half an hour in the plane, so when we arrived to Harbin, I immediately went to bed 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, when he told us "Give me 100 push-ups each!". Chen and Ulf protested, so I had to make these push-ups 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 Google Photos.

NWERC 2009 and One Night in Amsterdam

Last weekend I went to Nuremberg in Germany to represent KTH in a collegiate programming competition. Our team (me, Ulf and Chen) ended up on the third place out of 64 teams and we advanced to the World Finals in China! The event will take place in Harbin from 1st to 6th February and we will also see Harbin International Ice and Snow Sculpture Festival.

Some people considered us to be favorites and at least I am not happy with our performance. All 3 of us had a bad day. The start was fine, but after that we had 3 bad hours. Luckily, we managed to submit 3 correct solutions in the last 40 minutes, which moved us from the 12th place to the 3rd. As usual, I had most of my good ideas on the toilet. In the end I went there quite often. And we also managed to stay calm and focus in the end. 30 minutes before the end I had the courage to delete 30 lines of code and rewrite them from the beginning. It worked!

The organizers really surprised me. We got a prize (2 bottles of red wine) for printing a lot. During the contest the competitors are allowed print their code and some related stuff. We had lots of bugs and our strategy is to debug on paper. I think we printed at least 50 pages and at most 2 at a time. Thanks to us, the people responsible for printing were not bored. On the other hand, printing a lot is considered as bad behavior. I guess we printed the maximum amount which is not yet considered as bad.

After the contest we flew to Stockholm via Amsterdam. Unfortunately, because of fog in Amsterdam, we got stuck at the airport. Hotels were full and our flight was early in the morning, so we decided to stay at the airport. We played dice and then I decided to sleep while others continued playing all night. I woke up when something hit me. It turned out to be a piece of ice. I thought it was Ulf or Fredrik who threw it at me. But few hours later somebody told me that the waitresses at the Starbucks Coffee were throwing ice at people who were sleeping there. Few people suggested that this could also be a sign of attraction, so I guess I will return there in a few weeks and ask them "What did you mean by throwing ice at me?".