ACM ICPC World Finals 2011
Disclaimer This is an unofficial analysis of some possible ways to solve the problems of the ACM ICPC World Finals 2011. 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 | To Add Or To Multiply |
| B | Affine Mess |
| C | Ancient Messages |
| D | Chips Challenge |
| E | Coffee Central |
| F | Machine Works |
| G | Magic Sticks |
| H | Mining Your Own Business |
| I | Mummy Madness |
| J | Pyramids |
| K | Trash Removal |
A common theme that recurred in many of this year’s problems is guessing: guess a part of the answer, and then with this part fixed do some computations to see if the guess leads to a correct answer. (Of course, the details of exactly what to guess and how to figure out if the guess leads to an answer differs.) Problems where this applies are: A, B, D, I, and K.
Regarding the difficulties of the problem, my guesses were even more way off than usual. I had expected problem B to be the second easiest problem which turned out to be way off (never underestimate the deterring effect of a large mass of text...). Instead, the two easiest problems turned out to be C (which I did guess) and K (which I should have guessed but somehow did not). Almost all teams solved both of these. The next chunk of problems were E and J, both solved by slightly more than half of the teams. Continuing in the same pattern, problems A and H, were solved by roughly a third of the teams. The remaining problems were less popular, with at most 7 solutions for each. Problem D was the only one that was not solved.
Here are the stats of how many solutions there were1:
| Problem | A | B | C | D | E | F | G | H | I | J | K |
| Submissions | 138 | 36 | 192 | 12 | 223 | 33 | 107 | 195 | 10 | 396 | 297 |
| Solved | 35 | 7 | 98 | 0 | 63 | 2 | 7 | 39 | 2 | 60 | 94 |
As an additional curiosity fact: the judges were somewhat worried this year that some team would solve all 11 problems. We estimated roughly 4 hours of coding time to solve all problems. Of course, this does not take debugging time into account or the fact that it is almost impossible to utilize the computer at a 100% efficiency. Turns out the problemset was more than hard enough, as usual.
Congratuliations to Zhejiang University for winning their first ICPC World Champions title!
1 Seven of the submissions to problem D were actually submissions to problem C.