1 June 2011 Comments Off

ACM-ICPC World Final 2011 Problems – by Petr Mitrichev

I couldn’t stop myself from sharing a nice post from Petr Mitrichev’s blog:

“(…) 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 :) …”

30 May 2011 Comments Off

The 2011 World Finals Ranklist – ACM International Collegiate Programming Contest

The 2011  World Finals Ranklist – ACM International Collegiate Programming Contest. See live cast:

http://scrool.se/icpc/wf2011/

http://www.icpclive.com/?page=live333#

photo by Bettina Johnson

John Bonomo, ICPC World Finals chief judge, has been part of the judging team since the 2002 Honolulu competition. “Our main purpose is to handle any slight problems with the test data, look at problems that contestant teams continually get wrong, and for clarification,” he said. Bonomo explained how the judging process has become increasingly automated with the advancement of technology. “We used to look through code and run testing,” he said. “Now the satisfaction comes from crafting challenging sets of problems.”

According to ICPC director of judges Jo Perry, there is one judge per problem in the World Finals. The chief judge and director of judges are used as extra hands during the finals and are also responsible for putting the problem sets together for the competition. Perry became involved with the judging side of the competition after being asked by a colleague at North Carolina State University to submit problems to a then infant ICPC competition.

Some of the judging staff became involved with judging simply for their love of the ICPC. Originally born in Sweden and now living in Canada, Per Austrin became involved with the competition as a contestant for his Swedish university. He joined the judging team when he could no longer compete due to age and has been a regular World Finals judge since 2008. “I enjoy the contest,” he said. “The construction of problems is almost like the other side of solving them.”

Former Google programmer Derek Kisman got his start with the World Finals as a contestant for The University of Waterloo during the Prague competition. He said, “I love the ICPC and being behind the scenes now as a judge.” Kisman enjoys coming up with problems that spawn interesting discussions and plans to continue judging for the ICPC as long as possible.

While many on the judging team have always known the international programming competition under the familiar ICPC name, Stan Wileman remembers the forerunner to the official contest we know today. While attending the University of Houston as a graduate student, Wileman and his early team of programmers learned of a contest at Texas A&M. “We overslept the day of the completion and arrived at the tail-end,” Wileman said. “We were late but still managed to win the damn thing and split the $100 grand prize!”

Today, Wileman has earned two hats with the ICPC as a World Finals judge and the regional director of North Central North American region. Bettina Johnson, ICPC Digital

Live Ranklist

http://scrool.se/icpc/wf2011/

3 April 2011 Comments Off

ACM-ICPC 2011: From Egypt to Orlando!

ACM-ICPC 2011: From Egypt to Orlando!

I was wondering how the ACM-ICPC will be held in Egypt in the current scenario. Anyway, not to worry, The 2011 ACM-ICPC World Finals sponsored by IBM has been rescheduled in Peabody Orlando Hotel, Orlando, Florida
May 27-31, 2011.

According to Bill Poucher:

“Originally, we planned to have the World Finals in Egypt in 2014 or 2015. We have switched back to that plan due to recent events. While we could have had the World Finals in Sharm El Sheikh last week, transportation through Cairo has been difficult. Now with Consular Travel Advisories, it is not an option.

We hope… to reschedule so that you could all experience Egyptian hospitality at its finest. In the meantime, let’s wish our friends a safe path to a better future….”

The tentative schedule is as follows ( at http://www.peabodyorlando.com/):

  • May 27 – Welcome
  • May 28 – Tech Trek, Excursion to Sea World
  • May 29 – Opening / Rehearsal,
  • May 30 – World Finals, Awards Dinner, Harry Potter Island Celebration
  • May 31 – Teams Depart
  • May 31 – RCD Symposium
  • June 1 – RCDs depart

Best wishes to all qualified WF, ACMer’s- from ACMSolver.org (Ahmed Shamsul Arefin)