2009 ACM Programming Contest Results and Webcast

Jon Larsson writes "Yesterday, the 33rd World Finals of the ACM International Collegiate Programming Contest were held at KTH — The Royal Institute of Technology in Stockholm, Sweden. World Champions, for the second consecutive year, are the Saint Petersburg State University of IT, Mechanics and Optics. They won in competition with 99 other teams from all six continents — the best of the over 7000 teams participating in the qualifying rounds during the past half year. The full results can be found here and the contest problem set is available here (PDF). For the first time ever, the whole event was broadcast live, both on the web and on national TV in Sweden. The broadcast was produced by media students of KTH and the Lillehammer University College in Norway. The webcast in its entirety (over 7 hours) can be viewed here."

Comments

6 continents?

[cwebster]

Last time I checked there were 7.

"All 6 continents"? WTH?

[Itninja]

There's this cool place down South called Antarctica. People even work there: http://en.wikipedia.org/wiki/Demographics_of_Antarctica

Recursion

[MrEricSir]

Is it just me, or can 90% of the problems in ICPC be solved with brute-force recursive solutions?

Seems to me they could make things more interesting if they added a time complexity restriction to each problem.

Re:Recursion

[-kertrats-]

There is actually a time component - if your program takes too long to run, it will be counted as a failed attempt. The exact time barrier has varied from competition to competition when I've competed, however, they were all low enough to ensure that brute-forcing a problem only worked for very simple problems and not anything of any complexity. More interesting approaches will generally be needed to get credit for a solution.

Re:Recursion

[kristoferkarlsson]

Also, all problems are designed with a specific algorithm in mind, leading to a required time complexity.

The secret program inputs are then be designed to be large enough to be solved much much faster than the time limit with the correct complexity, but much much slower than the time limit with the wrong complexity.

You can typically look at the problem specification to see what the maximum input size is - and you should expect that you _will_ get inputs of that size, and do a rough estimate of how many operations that will require with your solution.

I've been in a competition where I used a O(n^2) algorithm where I didn't see the O(n*log n) solution (No it wasn't sorting, it was a Dynamic Programming-problem). I was convinced for a fairly long time that my algorithm was fast enough, so I spent time suboptimizing instead of solving the root problem - the wrong algorithm.
With the right algorithm, it passed right away.

That said, some problems are indeed expected to be solved by brute force, or by a combination of brute force and tricks to shrink the search space. These problems can mostly be identified by guarantees of small inputs in the description.

Re:Commentary

[Mad Merlin]

Thankfully, there's no .NET allowed at the ACM competitions, or at least there wasn't in any of the ones I participated in. C++, C and Java only. You also don't get any IDEs, or debuggers, or vim or emacs. There's vi, nano, a graphical editor with almost as many features as notepad and (IIRC), jove.

Re:Bogus Competition

[Keyper7]

1. Wrong. I never participated in those contests myself, but I know a lot of people who love them, and they are clear about it: russian and chinese programmers are very good. If you want proof, some contests allow non-participating watchers to peek at the code development in real time. Furthermore, in harder competitions, some of the problems are so hard people can spend days trying to figure out how to solve them in theory. Knowing the problems and the input data in advance sometimes doesn't mean shit.

2. Wrong. The problems are simple, but they allow uncountable small variations that could change the required approach completely. The competition rewards people with enough experience and instinct to know which approach, dynamic programming, greedy programming, brute-force with prunning, etc, will work best. Memorizing a book on calculus won't make you able to solve quickly any problem that only requires knowledge from this book. It's the same case here.

3. I didn't understand this point very well, care to clarify? They do solve the problem. The solution they have came from a fully functional executable solution to the problem.

4. Most of this is not on purpose. It's just that they judge is automatic, there's a limit on what an automatic response can say.

As for your conclusion, read my response to point 1 again. Without thinking, you don't go very far.