2009 ACM Programming Contest Results and Webcast 49
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."
6 continents? (Score:2, Informative)
Last time I checked there were 7.
Re:6 continents? (Score:5, Funny)
Re: (Score:2)
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 [wikimedia.org]
Re: (Score:2)
Last time I checked there were 7.
(Score:2, Informative)
Oh dear....
Re: (Score:2)
Not a lot of programmers native to Antarctica.
[Insert Linux penguin joke here]
Re:Only six continents? (Score:4, Funny)
Yes,
0 - Africa
1 - Antartica
2 - Asia
3 - Australia
4 - Europe
5 - North America
6 - South America
Re: (Score:2)
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: (Score:2)
See here [wikipedia.org].
Re: (Score:1)
"All 6 continents"? WTH? (Score:2, Informative)
Commentary (Score:4, Funny)
And now you can see Alxei execute this beautiful node assignment in hex. Gordon whats your take on the use of
Well Steve I'm glad you asked....
Re: (Score:3, Informative)
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: (Score:2)
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).
Correction (Score:3, Funny)
The girl's ass.
Recursion (Score:3, Informative)
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 (Score:5, Informative)
Re:Recursion (Score:4, Informative)
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: (Score:3, Insightful)
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.
Oh Joy! (Score:1, Troll)
I remember when we were in the top 2... (Score:2)
...heck, I was there [plambeck.org].
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 he
Re: (Score:2)
Bogus Competition (Score:2)
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. Im
Re:Bogus Competition (Score:5, Informative)
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: (Score:2)
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 schedu
Re: (Score:2)
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. S
Re: (Score:2)
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 offe
Re: (Score:3, Interesting)
icpc-2009-world-finals.html [blogspot.com]
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: (Score:1)
Introduction to Algorithms [wikipedia.org] 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.