Nordic championships in programming 2015: behind the scenes

Nordic championships in programming 2015 (NCPC 2015) took place three weeks ago and I was the head of the jury for the third time in a row, together with Markus Dregi from University of Bergen. Last year I’ve written my impressions from behind the scenes and I’d like to continue with the tradition. Let me first mention 2 problems that I liked.

H – Hero Power

Hero Power involved a simplified Guitar Hero game. On Tuesday September 29, about 10 days before the contest, the task still hasn’t been solved by anyone from the jury. Not even Björn had solved it, the author of the task who worked on it for a couple of months. In addition to many rules that were also present in the final problem statement, at the time there was an additional rule that the SP meter charges by extra 5 seconds at the end of every SP phrase (the so-called 5-second rule).

The contest was near, so me, Björn and Oskar decided to have a meeting on the sunny roof of Spotify’s office. We wanted to simplify the problem but it wasn’t clear how. I claimed that combining continuous charging with 5-second bonuses makes it hard to solve: when you draw the content of the SP meter as a function of time, you get a non-continuous function and such functions are hard to grasp. In this version, it’s not enough to charge in continuous chunks, because taking breaks allows you to collect just the right amount of 5-second bonuses. This complicated the solution greatly.

I suggested removing the 5-second rule but keeping everything else as it is. Björn disagreed. It was getting colder on the roof and we had music to stream, so we agreed to disagree. I wanted to ask the rest of the jury for opinions and also write a solution myself. Perhaps my modification wasn’t that elegant anyway.

After dinner I sat down to write a solution. It was an obvious dynamic programming problem, but the update step turned out to be very tricky. After about 30 minutes of thinking I finally got it and wrote a super-short solution. It felt too short for such a hard problem, so I proved its correctness 2 more times to convince myself.

I mostly liked lines between 41 and 50, which contain dynamic programming, greedy strategy and amortized complexity on a very small space. Even the preprocessing step is non-trivial and uses the ‘resize’ function in C++ ‘vector’ in an elegant way.

I had one of those rare moments when you are taken aback by a beautiful computer program. It was even more rare, since the code was mine. The problem version without the 5-second rule turned out to be awesome on many levels, so I went to defend it on our mailing list.

I've just implemented a solution for the version without the 5-second rule and I'm stunned. This is pure poetry! 

The task is a beautiful mix of dynamic programming, greedy, amortized complexity and clever data structures (just arrays and hash maps, but clever still). All the steps are non-trivial to make it run in O(np).

My excited e-mail was enough to convince everyone to remove the 5-second rule. In the end it was still very hard and only 2 teams solved the problem.

I – iCar

In this task you have an iCar with only one button – when pressed, the car accelerates with the rate of 1 meter per second per second. Once you release the button, the car stops immediately. (Side note: we have considered adding braking instead of immediate stop, but the problem was already too hard.)

This is yet another task that was shaped greatly with time and with the help of the rest of the jury (thanks a lot, Marc!). Andreas Lundblad sent us a suggestion already in May and it was basically the same problem as it appeared in the contest. He could only solve it for one semaphore, though. I managed to figure out all the cases needed to solve it for 2 semaphores, so I told him we’ll take the problem and figure out the details later. At worst we have the 2-semaphore version, but I was curious about extending it to 5 or even 100 semaphores.

In the end we went with 20-semaphore It was a lot of work and it took us a more than a month to get it right. First, Marc generated test cases, but my code was able to find a shorter route to the finish. Later, Marc found the nasty case shown below that broke my solution instead.

The crucial step in solving the problem is choosing the right visualization. There are two important parameters, the position of the car given in kilometers from the start and time since the start. The third interesting parameter is speed, but you can actually skip that and infer it instead.

Two parameters can be visualized in 2D: the picture below has time rising from bottom to the top and position from left to right. It contains a solution that illustrates all the different cases a correct solution needs to handle. Red vertical lines denote red lights on semaphores. Blue parabolas and dots denote a car that is accelerating and stopped respectively.

Solution to 000-random-seed-144.in. Marc also created visualizations for all test cases that you can download from the contest webpage. 

The second parabola is passing the 5th semaphore at the last moment of a green light and then passing the 10th semaphore at the earliest moment of a green light. We could have passed the 5th earlier, but we’d have to have lower speed to avoid hitting a red light on the 10th. This strategy allows us to pass the 10th semaphore with the highest speed possible.

While this might sound complicated, we're still not done and it's only enough to solve the 2-semaphore version. To solve the problem with 20 semaphores, you also need to handle two more cases, which are the last two parabolas in the picture.

The very high speed we acquired allows us to be at the 12th semaphore during a red light. We could stop at the semaphore and wait there for a green light, but a better strategy is stop earlier, so that we can start accelerating earlier and have higher speed when the 12th semaphore turns green.

Finally, we stop before the 13th semaphore and start accelerating, so that we pass it at the last moment of a green light. Such waiting strategy paradoxically improves the time in the finish. A little bit of calculus can prove that.

In the end no one solved the problem and I kind of expected that. One could argue that this problem should have been saved for a more difficult stage like NWERC or World Finals, but I’m not sure. Even small contests like NCPC need hard problems to stop the best teams from solving everything.

Overall this is one of the top problems I helped preparing for a contest, because quadratic geometry is very unusual in programming contests.

The bad

Apart from fun problems, a couple of things didn't pan out so well. Problem G was solvable with brute force if you managed to optimize it well. Problems D and E were too similar. Too many pproblems were dealing with time events.

We knew about these issue before the contest, but it was too late to change things. We already skipped some problems and were down to 10 when we discovered issues with G. Skipping one more problem felt like a worse decision than keeping it.

We could have prevented it if we received more problem suggestions and more people were helping out. If you would like to prevent similar situation from happening, please send problem suggestions next year. Don’t hesitate even if you aren’t skilled in preparing competition problems, because there’s always other jury members that can help you out. For example, Hero Power and iCar were suggested by people with little jury experience and then received a lot of help from the rest of the jury.

Conclusion

If you like the stories from behind the scenes, don’t hesitate to get involved next year! You can mail me at [polacek (at) kth dot se] and I’ll add you to the right mailing lists.

I’ve now left Scandinavia and after 3 years as a head of jury I’ve quit. I’d like to be involved though and contribute a problem or two next year. I hope the quality of NCPC stays very high!