← Problem set

Disclaimer This is an unofficial analysis of some possible ways to solve the problems of the ACM ICPC World Finals 2013. The writeups for problems B and I are written by Jakub “Onufry” Wojtaszczyk. Should an error be found, we will blame each other for the cause, but I would be happy to hear about it at austrin@kth.se.

Also, note that these sketches are just that—sketches. They are not intended to give a complete solution, but rather to outline some approach that can be used to solve the problem. If some of the terminology or algorithms mentioned below are not familiar to you, your favorite search engine should be able to help.

— Per Austrin

Summary

My guesstimated order for the problems to be solved was AFJDCHBKIEG The actual order in which the problems were solved was FDAJCHEIKB, with G left unsolved. In terms of number of teams that ended up solving each problem, the numbers were:

In total there were 430 Accepted submissions, 815 Wrong Answer submissions, 315 Time Limit Exceeded submissions and 79 Run Time Errors. The most popular language was C++ by a wide margin: 1347 submissions compared to 323 for Java. There were no C submissions.

Congratulations to St. Petersburg State University of IT, Mechanics and Optics, the 2013 ICPC World Champions for their awesome performance! They were very very close to being the first team ever to solve all the problems at a World Finals. This is how close they were: the best of their many attempts to solve the last problem (Map Tiles) were only stopped due to a few extra cases that we added shortly before the contest (on those cases, their code used more than 5x the time limit). Maybe the following pictures give an indication of the excitement in the judge’s room during the last few minutes of the contest.

In case you are wondering what those last three cases where, they are depicted on the last page of this document (if I remember correctly the submissions failed all these three).

Subnormal behavior. The heroes of the day in the judging room were the University of Tokyo with their work on problem B (Hey, Better Bettor). Their initial solution was fast enough (but a close call) on the hardest cases but then timed out (with a wide margin) on a seemingly simple test case. This was very confusing to us, because the code was very simple, and looked like it should run exactly the same instructions with exactly the same memory access patterns, regardless of the input case. This caused a lot of head-scratching and headache and occupied the better half of the judges and the Kattis group for quite a while. Fortunately the Tokyo team rescued us from our worries by figuring out how to fix their code and got the first accepted solution to the problem. The issue turned out to be the following: in their solution they were precomputing all the powers 1, p/(1−p), (p/(1−p))², (p/(1−p))³, . . . up to some number. After a while, the numbers became very small but non-zero, and for some values of p they reached long sequences of subnormal floating-point numbers. Unfortunately, calculations on subnormal floating-point numbers can be really slow. Adding an if statement that zeroed out the number if it was less than 10⁻¹⁰⁰, their solution became 10 times faster. A good lesson to learn!

A note about solution sizes: below the size of the smallest judge and team solutions for each problem is stated. It should be mentioned that these numbers are just there to give an indication of the order of magnitude. The judge solutions were not written to be minimal and it is trivial to make them shorter by removing spacing, renaming variables, and so on. And of course the same goes for the code written by the teams during the contest!