Tuesday, May 31, 2011

Reflections on ACM ICPC 2011 World Finals Problems

I've taken some time to reflect on the World Finals problems - hopefully that will be interesting for you to read. If you were not following the World Finals closely, you should probably skip this post :)

The problems are at http://cm.baylor.edu/digital/icpc2011.pdf, the unofficial solutions from Per at http://www.csc.kth.se/~austrin/icpc/finals2011solutions.pdf.

I've really liked the problemset, so please don't take my words below as criticism - I've just tried to look at the problems from different angles and classify them in different ways, and maybe suggest some improvements for the future.

Problem A - To Add or to Multiply - ad-hoc (number theory?) (by ad-hoc I mean "need creative thinking to solve but no necessary prior algorithm/mathematics knowledge or experience solving similar problems"), most difficulty in corner cases and finding the lexicographically smallest answer.
Problem B - Affine Mess - exhaustive search (do what's described in the problem statement) + solving a system of 2 linear equations, most difficulty in corner cases.
Problem C - Ancient Messages - ad-hoc, out-of-format problem, as there's no precise definition of valid input.
Problem D - Chips Challenge - maximum flow (reduction to flow is the most difficult part).
Problem E - Coffee Central - exhaustive search (do what's described in the problem statement) + the набившая оскомину idea about using inclusion-exclusion for rectangle sums. Most difficulty in finding the lexicographically smallest answer.
Problem F - Machine Works - DP plus incremental convex hull within one quadrant. The key to producing NlogN solution is the somewhat well-known idea about incremental convex hull to find the maximum of a set of linear functions. Most difficulty is inventing this speedup (if not known in advance) and implementing incremental convex hull.
Problem G - Magic Sticks - ad-hoc, geometry. The solution has two main parts - inventing and then proving (or believing) the key mathematical fact about throwing away the longest edge, and solving a sub-problem where you have to maximize the area of the polygon with the given sides. The sub-problem is again quite well-known and was a significant advantage to the teams who saw it before. However, I believe the most difficult part was the longest edge fact. There was also a catch about one edge taking more than Pi angle which many teams forgot to account for.
Problem H - Mining Your Own Business - graph theory, ad-hoc. The most mathematically beautiful problem of the contest in my opinion. The main difficulty is constructing the "if and only if" condition for the set of escape shafts.
Problem I - Mummy Madness - interval trees (or priority queues), ad-hoc. The main difficulty is realizing (a.k.a proving or believing) the problem can be reduced to checking if a square is completely covered by a set of squares. The NlogN solution to that sub-problem is very well-known and should be very easy for top teams.
Problem J - Pyramids - quite straightforward DP (backtracking should also work). I don't see any significant difficulty at all here, but if I were to choose the main difficulty, it would be building the lexicographically largest answer in the DP solution.
Problem K - Trash Removal - a well-known problem. Solvable in NlogN using rotating calipers, but since the constraints were so low, that solution is an overkill. The only difficulty with such small constraints was to realize that the line should be parallel to the line connecting some pair of vertices. The main difficulty is the geometric formulas, but those are very easy as well.

Problem H was really standing out from the problemset, in my view, because it required graph theory thinking but at the same time involved no heavyweight algorithms or implementation difficulties. I would love to see more problems like this, but they are very hard to come up with. Problem C is unusual (so one might argue it gets close to the boundary of teams might reasonably expect) but still good. Problems E, F, I, J, K are "professional" problems - the most difficult part of each lies in a "standard set of tools" that most competitive programmers hone from contest to contest. This is not a negative thing - those ideas form the standard set of tools exactly because they're most useful "building blocks" of various algorithms. Problem K may be too well-known though. Problem G is borderline as it combines a beautiful ad-hoc part with quite difficult algorithm that might be well-known to some teams but not others. Problem D is borderline (but still very good in my opinion) because the "reduce to maximum flow" trickery can also be viewed as a part of "standard set of tools", and thus the problem is quite "professional" too. Problems A, E, J require relatively little thought, and have main difficulty in figuring out the corner cases and careful implementation, which is not exciting, and I'd say 3 such problems is too much (but maybe I'm too subjective after several teams I've supported got buried in those issues).

To spice up the long text, here's my picture with the World Champions:


Please share your thoughts :)

11 comments:

  1. Alexey RudakovskyMay 10, 2013 at 1:37 PM

    funny pic - nice product placement :)

    ReplyDelete
  2. No. Too old :)

    ReplyDelete
  3. I'd say no.

    ReplyDelete
  4. Is this the first time any girl figures in the World Champion team?How many girls are there on topcoder who are red ?I am asking all these because in our parts of the world we rarely get to see a girl taking interest in these.

    ReplyDelete
  5. The picture is definitely hilarious

    ReplyDelete
  6. Seyed Hamed ValizadehMay 10, 2013 at 1:37 PM

    Where is problem H? I don't see it in problem set PDF.
    EDIT: Sorry! I thought H is after K! Look at the post :D

    ReplyDelete
  7. http://cm.baylor.edu/ICPCWiki/Wiki.jsp?page=Problem%20Resourcesjust realize that this year they made the test data public

    ReplyDelete
  8. Davidcarvajal586May 10, 2013 at 1:38 PM

    man i wanted to add you in facebook how is your nickname?

    ReplyDelete
  9. congratulations to the winner

    ReplyDelete