ACM ICPC World Finals 2016
Disclaimer This is an unofficial analysis of some possible ways to solve the problems of the ACM ICPC World Finals 2016. 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. If you find an error, please send an e-mail to austrin@kth.se about it.
— Per Austrin and Jakub Onufry Wojtaszczyk
This year provided some exciting behind-the-scenes action that we fortunately managed to keep away from the teams during the contest. Long story short, at 10 in the evening the night before the contest, we realized that one of the problems was irreparably broken – four different judges had come up with precisely the same natural but very subtly incorrect algorithm, we had no correct solutions, and the problem suddenly looked a lot harder. Fortunately, we had preparations for such eventualities, and we had another problem ready (J – Spin Doctor) that was a somewhat suitable swap-in for the broken problem. Several hours later, the judges had become very skilled at unstapling problem sets, replacing pages, and re-stapling them. This last minute change made the problem set harder than we had originally intended, and it would probably have been sufficient to stick with 12 problems and not swap in the new problem.
We’ll see if we can figure out how to solve the broken problem until next year, maybe you will some day see it in some form...
Congratulations to St. Petersburg State University, the 2016 ICPC World Champions!
In terms of number of teams that ended up solving each problem, the numbers were:
| Problem | A | B | C | D | E | F | G | H | I | J | K | L | M |
| Solved | 36 | 50 | 128 | 51 | 92 | 12 | 96 | 0 | 1 | 2 | 66 | 108 | 8 |
| Submissions | 123 | 192 | 160 | 87 | 357 | 32 | 416 | 1 | 22 | 43 | 203 | 402 | 26 |
In total there were 650 Accepted submissions, 1210 Wrong Answer submissions, 158 Time Limit Exceeded submissions and 46 Run Time Errors. The most popular language was C++ by a wide margin: 1904 submissions compared to 161 for Java. There were exactly zero submissions in C, but on the other hand all of them were accepted.
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!