← Problem set

Disclaimer These are unofficial descriptions of possible ways to solve the problems of the ACM ICPC World Finals 2010. 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

Summary

Before the contest, I expected problem B to be easiest followed by C and D and then G and J. When the first solutions started coming in for J then G then D it dawned on me that I was wrong as usual. In the end, I think problems D, G, and J ended up being tied for easiest with 78 teams solving each of them. Problem C was solved by almost the that many teams and problem B by roughly half that. All problems ended up being solved, but problems A, E, and H only by one team each. This was also somewhat surprising to me: I did not believe anyone would solve A, and that H would be solved by several teams. I also believed that Problem I would be solved by more teams, but given that it is a brute-force problem and it is hard to know how much pruning is necessary I guess it is not suprising that many teams were hesitant to spend time on it.

Congratulations to Shanghai Jiaotong University for their third ICPC victory!