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.

Re:6 continents?

[The Hooloovoo]

Yes, for the 33rd year running, the Antarctic universities were unfairly excluded from this competition.

Re:6 continents?

[PIBM]

Actually, depending on where you live, you will get to learn different numbers.

Here are shown the common ways to split the continents:

http://upload.wikimedia.org/wikipedia/commons/7/77/Continental_models.gif

Re:6 continents?

[Tubal-Cain]

Last time I checked there were 7.

(Score:2, Informative)

Oh dear....

"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

Re:Only six continents?

[Quiet_Desperation]

Not a lot of programmers native to Antarctica.

[Insert Linux penguin joke here]

Commentary

[KingPin27]

"The webcast in its entirety (over 7 hours) can be viewed here...."
And now you can see Alxei execute this beautiful node assignment in hex. Gordon whats your take on the use of .NET to complete this challenge?
Well Steve I'm glad you asked....

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:Commentary

[piojo]

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.

That really depends on the place you participate in the contest. (It is probably more controlled at the national level.) When I participated in an ACM contest last year, they did not care what IDEs we used--we could even install additional IDEs. They were similarly free with documentation, but I think they wanted us to download it in advance (no google searches during the contest).

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:Recursion

[MrEricSir]

In my experience with both ICPC and TopCoder, they only test the solution with "toy" examples on a relatively fast machine.

That's not the same as saying your solution has to be, for example, O(n) or better.

Re:Only six continents?

[Anonymous Coward]

Yes,

0 - Africa
1 - Antartica
2 - Asia
3 - Australia
4 - Europe
5 - North America
6 - South America

Re:Only six continents?

[Tubal-Cain]

Europe/Asia can be considered one continent, as can North/South America.
See here.

Correction

[Sybert42]

The girl's ass.

I remember when we were in the top 2...

[jeffb (2.718)]

...heck, I was there.

The top two teams were the only ones who solved all six problems. We were separated by a few hours of cumulative time, and I still attribute that difference to the fact that we were stuck with a Hazeltine ultra-stupid terminal instead of the ultra-smart HP terminals that some other teams got. If we'd had Stan on one of the HP's, it would've saved us significant time, test runs, and distraction. (Test runs, and incorrect submissions, both carried time penalties.)

And I don't want to hear whines about vi. We were stuck using a bespoke command-line text editor, in a bespoke limited shell.

Re:I remember when we were in the top 2...

[jeffb (2.718)]

I believe there was one token European team the year I went (1984), and I think that might have been the first year they billed it as "International". It certainly wasn't drawing from so wide a talent pool then as it does now.

Bogus Competition

[0xABADC0DA]

1. A good team just getting its hands on the test data beforehand, let alone the problems, will win hands down. The two countries most likely to do this IMO, China and Russia, are the winner and runner up. I don't mean to presume the worst or disparage their programmers, but I certainly don't trust the ACM to secure this very well.

2. The problems are not unique and are usually very simple. The competition rewards people that memorize past problems and solutions, and can regurgitate the code quickly.

3. Important test data is withheld, meaning there is a lot of time wasted by asking for clarifications. And answers to clarification are often mysterious as to hide important 'gotcha' test data. The ACM acts like if they give out actual test data then the programs will be hard-coded. But that's only the case if you give out all of the test data. If the test input is "3.3" you have other input that is "3.4" that you don't give out and then they have to actually solve the problem.

4. Failures are purposely made hard to correct. If your program is not 100% correct the result is "Invalid output" or "Crash". You have no idea what is wrong, so you just have to guess at what is not correct. In some cases the test data itself has been wrong (not valid according to problem description), and invalid programs have been accepted because they made the same wrong choices as the people creating the test data.

Some people will say those things I listed are just part of the challenge. Ok, fine, but in the end they make the competition about the ability to recite code and to anticipate inputs; if you expected thinking to be involved you're sorely mistaken. As a measure of what I think most people would consider programming skill this competition is bunk.

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.

Re:Bogus Competition

[0xABADC0DA]

Ok well a while back I was on a team that placed 3rd in ACM regionals and I was 93% on topcoder and still rising pretty fast after just a couple weeks. This was the practice team; our #1 team placed 4th internationally that year irrc.

1. If you know the problems ahead of time then you'll win. End of story. I'm not saying the Russians or Chinese had the problems ahead of time, but this is the nature of the competition.

2. Our practice was to get up on Sunday morning at 8 or 9am (depending on football schedule?) and redo old problems from regionals and finals. This is what all high placing teams did to practice. The problems are simple, and you can pretty much instantly figure out the right approach. Deciphering the poorly-worded questions to figure out what the actual problem is, is another matter. I don't get up at 8am on a Sunday, sorry. ;-P

3. For instance an asteroid early warning system, with gotcha data of asteroid first seen at coordinates 0,0 and last seen at 0,0. One team put in a clarification for this and was not answered directly ("refer to the problem description" or something like that). This is gotcha test data that has no bearing on the actual solution to the problem. This data is withheld to make the problem harder, when a good competition would have harder problems.

4. Wrong. When you program crashes they could return you the test data it crashed on for instance. You're already penalized 20(?) minutes for each incorrect submission, so the only reason not to do this is to put up fake walls to solving the problem.

You don't have to take my word for it, but ask other people who have actually done this competition instead of just armchair quarterbacking it.

Re:Bogus Competition

[bzipitidoo]

I have participated in, and won, and lost these ACM and Topcoder contests. And the GP has some points.

Often, success in these contests is very arbitrary. Just look at the typical results. Massive spreads and inconsistencies. Bookies would have a harder time figuring the odds for this than for most sports.

I think the format of the typical contest promotes this. Anyone can have a bad day. There's no time to recover from mistakes and there's so much more that can go wrong than in, say, a footrace. Suppose the computer you are assigned is a little flaky, so that once in a while your programs randomly crash for no reason. Or a technique you use is perfectly valid except that it fails thanks to arbitrary language or compiler limitations exposed by lengthy test data. Maybe there are several approaches to a problem, and it's not clear which way to go. What you'd like to be able to do is try 2 approaches, and use them to check each other's results, but the time pressure is extreme, so you must choose. Maybe both are about equally easy to whip up quickly in which case the choice doesn't matter, and maybe not. Choose right and you may be a winner. Choose wrong, and you're out of the running. There's also the problem of dealing with very poor test data, and you haven't time to produce and verify good tests that check corner cases and such, so it's all write and pray. You could argue much of that is all part of the contest, and it's the participants' business to know about such things, but I think that detracts from the validity of the results. It's like a hypothetical race in which the track has fork after fork and blind corners and hills, and no one gets to see the track beforehand.

Nothing quite so infuriating as having a good answer, and knowing you have a good answer, but not being able to get the submission to pass. Could be a rounding error-- I've had a program that ran correctly on my computer rejected because the compiler on their end was not as careful with the math. The same program with the same data worked on my end, but didn't work on theirs. Granted, the code I wrote was prone to just such a problem and I knew that, but didn't learn it had happened until too late. Or, you've seen that sort of problem before, but can't quite put your finger on the solution-- until hours after the contest has ended. I also didn't like the way Topcoder's arbitrary rules punish you for making a submission. I thought I had nothing to lose and at the end of one contest submitted what I'd been working on, just in case the last few changes were enough, although I didn't think so. And someone who had no idea whether my solution was any good decided to take a chance on scoring some extra points based solely on the last minute submission time, and score they did. Not how that mechanism was intended to work, I suspect. That's working the rules, not working the craft.

Re:Bogus Competition

[sydneyfong]

I've been involved in these kinds of competitions a few years ago, in particular the Olympiads in Informatics (eg. IOI) and I've participated in a ACM regionals last year. I know close friends who have been competing in the World Finals, with pretty good scores.

I pretty much agree that the contest format has its problems, which is one of the reasons why I ceased to actively participate in these type of contests, but there's absolutely no reason to slander the winning teams.

I don't know what prizes they offer for the champion, but one of the most attractive benefits is bragging rights. Cheating sort of defeats the purpose of participating in such a contest, don't you think? Now that the tasks are made public, I'd wager that you wouldn't be able to solve 9 tasks even if I gave you a week.

So please. Don't be so juvenile.

I'll grant you one thing. The reason why Russian and Chinese contestants generally do better than those in America and Europe is because they relatively lack other distractions, and thus they are able to invest vast amounts of time into perfecting these admittedly "useless" skills that only apply to these "cute" contests. I've heard of stories about some teams undergoing "intensive training" and staying full time in the computer lab living off Ramen.

I doubt you'd do that. That's why you didn't win and they did. Hacking and cracking into the judges' systems? Not so much.

Re:Only six continents?

[pmarini]

you missed Middle East, EMEA and New Zealand (forgive me if they are not in alphabetical order)...

Re:Only six continents?

[vadim_t]

Nice try, but programmers still count the number of things the same way as everybody else.

If "contients" is a collection, then continents.Count will be 7, while continents.Min is 0, and continents.Max is 6.

Re:Source code of winning solutions

[Vexorian]

Not quite the source code but as it is an algorithm contest it should help understanding it:

icpc-2009-world-finals.html

As to languages, in the case of ICPC there are only C, C++ and Java. Other programming competitions allow more languages, most people use C/C++ in these contests anyway...

Re:Source code of winning solutions

[GrievousMistake]

Introduction to Algorithms isn't a bad read, and is likely to be the textbook used for any courses you take on the subject.
For everything else, there's Knuth.