ACM ICPC World Finals 2012
Disclaimer This is an unofficial analysis of some possible ways to solve the problems of the ACM ICPC World Finals 2012. Any error in this text is my error. Should you find such an error, 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.
Finally, I want to stress that while I’m the one who has written this document, I do not take credit for the ideas behind these solutions—they come from many different people.
— Per Austrin
| A | Asteroid Rangers |
| B | Curvy Little Bottles |
| C | Bus Tour |
| D | Fibonacci Words |
| E | Infiltration |
| F | Keys |
| G | Minimum Cost Flow |
| H | Room Service |
| I | A Safe Bet |
| J | Shortest Flight Path |
| K | Stacking Plates |
| L | Takeover Wars |
My guesstimated order for the problems to be solved was BKECLGDAFIHJ. The actual order in which the problems were solved was BDKLCEGIFA, with HJ left unsolved, which means I was less off than usual though I certainly overestimated problem D and underestimated problem E. 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 |
| Solved | 2 | 110 | 76 | 96 | 31 | 2 | 8 | 0 | 11 | 0 | 67 | 16 |
| Submissions | 51 | 202 | 251 | 278 | 300 | 29 | 45 | 12 | 113 | 0 | 289 | 90 |
In total there were 419 Accepted submissions, 924 Wrong Answer submissions, 243 Time Limit Exceeded submissions and 74 Run Time Errors. The most popular language was C++ by a wide margin: 1459 submissions compared to 220 for Java. There was also one single submission made in C (which was accepted, on problem B).
Congratulations to St. Petersburg State University of IT, Mechanics and Optics, the 2012 ICPC World Champions!