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?

[Anonymous Coward]

Article written by USAzien, give him a break.

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....

Only six continents?

[Anonymous Coward]

Aren't there seven widely recognized continents on this planet?
Africa
Antartica
Asia
Australia
Europe
North America
South America

Re:Only six continents?

[Quiet_Desperation]

Not a lot of programmers native to Antarctica.

[Insert Linux penguin joke here]

Re:Only six continents?

[Anonymous Coward]

Granted. But the story reads "99 other teams from all six continents", not "99 other teams from the six continents with native programmers."

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.

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.

"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

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).

Re:Commentary

[Anonymous Coward]

I don't know what ACM contest you were at but doing that is against ACM rules.

I placed in the atlantic canadian contest and went on to do the northeast ACM contest in RIT. We got to use vi and a graphical editor with very few features and we had to do it on whatever system was given to us, RIT had sun systems.

And you are only allowed bringing in a small bit of material with you, they have a limit on it and no electronic copies.

The film crew = perverts

[Anonymous Coward]

What the hell. :) During the first minute of "Award Ceremy 1" the camera zooms in on a girls ass.

Wild guesses

[Anonymous Coward]

Many more males than females. Those outside the first world work much harder because they have to, given recent xenophobia evident in the technology sector in particular.

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

[Anonymous Coward]

As a contestant whose team had solutions to 7 problems, 3 of which did not pass the speed test, I can say that they definitely did put large test cases in. (one had 100000 different input points)
Our O(n^2) algorithm was not as efficient as their O(n^2) algorithm and so was not accepted. Ya might want to check out the problem set before you post.

Oh Joy!

[Zontar_Thing_From_Ve]

How to great to know that Russia is number #1 for 2 years in a row. Now we can all look forward to these kids having long and successful careers helping the Russian mafia steal money from other countries, helping the Russian government to destabilize it's former USSR neighbors, and other such "fun" things that we'll all have to deal with.

Re:Oh Joy!

[Anonymous Coward]

How to great to know that US is not number #1. Now we don't have to look forward to these kids having long and successful careers helping the US government and financial companies steal money from other countries, helping the US government to destabilize it's other countries, and other such "fun" things that we'll all have to deal with.

Oh wait

Virginia Tech

[Anonymous Coward]

Sad to see VT not place. I remember when we were in the top 10. ;-(

R.I.P. Dr. Sally Henry

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...

[Anonymous Coward]

It seems that international countries only starting participating as of 1990, at which point the percentage of top teams from US universities started dropping. Probably dropped to the current performance levels post-bubble.

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

[Anonymous Coward]

I've actually competed for Purdue University. I competed in the Regionals, and our other team went to the finals this year.

1. Wrong. As Kevper said, the Russian and Chinese teams really are that good. In fact, even many of the American teams are composed by international students from Eastern Europe or Asia. Our team had 2 out of 3 from Kazakhstan.

2. Some of the problems are "simple" in the Regional level, but in the World Finals they all take considerable thought and experience to figure out.
Experience will help you do better at anything. Algorithms are no different. Of course people that have been in the contest in past years are going to do better. That doesn't mean their problems are unoriginal.

3. When I competed, clarifications were sometimes needed, and occasionally problem statements were too sparse on details, but usually this was not a big problem. They do provide some test cases (enough for most competent programmers to figure out, in my experience).

4. There have been times when test data was invalid, but this is very rare in my experience.
The fact that failures are "hard to correct" is a good thing. I believe the give you your output (if your program didn't crash), and that's really all the information they can give you. We're not using IDEs or other fancy tools to program things, so it fits the contest to do this.

In my opinion as a past competitor, this competition is excellent in testing algorithmic problem-solving capability and the ability to very quickly crank out code with few flaws, or be able to debug quickly and effectively.

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

[Anonymous Coward]

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.

Another reason behind not actually telling you where your program crashed is to avoid giving enough information for you to write a hack for specific input just to pass.

The time penalty also costs you if you're attempting to get details from the existence of a crash.

For instance, hardcoding
if (input = x) crashhere; and seeing if your result is "Incorrect output" or "Seg fault".

You can get your solution to pass the input data set this way, despite not having the correct solution to the problem.

Re:Bogus Competition

[Anonymous Coward]

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.

Most of the problems are different. Of course they build on the same principles, but it's not like you can memorize the code and just blindly type it in, if it was, I bet that explains why you finished 3rd.

Regarding the test data.. They don't disclose any correct data output in error messages for the obvious reasons, one could for example just hardcode to correct answer where your algorithm fails to calculate the correct answer.

Re:Bogus Competition

[Anonymous Coward]

You are sometimes given very lacking input examples for a problem or two, true, but you're supposed to write your own test data as you need it.
If you're told to "refer to the problem description", that means that they believe the specification is clear enough. You're likely to get it if you ask "Can situation X occur?" or something, when the constraints are clearly given, and you're supposed to correctly handle all possible input that fits them.

This is obviously intended, and means that the contest is also about reading the specifications and taking care to write correct code. You may have prefered a purer focus on efficiency, but I wouldn't call it a 'fake wall' any more than the running time limit or not using your cell phone.
If they gave you test cases for all the corner cases, you'd see a lot more people just shotgun debugging their way to a working implementation, which would be a shame IMO. Frantically triple-checking your printouts for whatever bug is causing your code to crash can be a very intense and enjoyable part of the competition. It's not just artificially 'making the problems harder' purely by frustration like, say requiring you to have only one line of code visible on the screen, it adds another dimension to the problem in that you have to find your own errors rather than just having the IDE highlight the faulty line.

Re:Bogus Competition

[Anonymous Coward]

it adds another dimension to the problem in that you have to find your own errors rather than just having the IDE highlight the faulty line. ... You may have prefered a purer focus on efficiency

I would prefer a focus on problems that aren't all basically the same, that require the participants to be creative rather than mechanical perfectionists.

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:Bogus Competition

[Anonymous Coward]

I would prefer a focus on problems that aren't all basically the same, that require the participants to be creative rather than mechanical perfectionists.

... and what exactly are you doing in the Engineering field then instead of say... Creative writing?

Almost all programming problems you "solve" have been solved before by somebody else and you reuse their solution, assuming it is perfect (or close to). You don't expect your kernel to be creative, you expect it to work, every time. Why should the code you write be any worse?

Re:Bogus Competition

[Anonymous Coward]

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.

So, just to take a stab at the REAL problem - you didn't win, you're unhappy that the *Russians* of all people beat you, and now you're harping on about how this OBVIOUSLY must mean that they cheated, because there's no way they could've beat you without it?

I'm not sure if you're arrogant enough to really believe that or dishonest enough to make such claims even though you don't, but in either case, I think you're a perfect example of a poor sportsman, old chap.

Re:Bogus Competition

[Anonymous Coward]

Hey! You were that darn team that beat us! I was at Cedarville and have been doing the ICPC for 3 years.

I definitely agree on 1., (although there are good US coders, there are a LOT of good foreign coders)

2. Absolutely. There are no repeat problems.

3. Absolutely. clarifications usually don't matter much.

4. I think maybe using a little more IDE support would be more realistic, but honestly, you waste time debugging your wrong code when you never understood what you were doing in the first place. The teams who understand what they're doing will find the problems by looking at the code. It's only a big hindrance for trial and error programmers who wouldn't win anyway.

We had a judging error not give us a correct answer on a problem for a few hours, but it would not have changed the rankings (even if we did get 5, we probably would not have passed Waterloo)

Re:Bogus Competition

[Anonymous Coward]

If you don't want a rep as cheaters, don't get *caught* cheating at the Olympics and pretty much any international competition like China, Russia, and communist Germany have. At least your programmers haven't been *caught* cheating yet.

Source code of winning solutions

[Anonymous Coward]

Is the source code of the winners posted? What sort of restrictions on languages are there? :)

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

[Anonymous Coward]

Hmmm... Since you say it's an algorithm contest, do you know of any books/websites, where I could start to learn algorithms? :)

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.