Forgot your password?
typodupeerror
Programming Education IT Technology Entertainment

2009 ACM Programming Contest Results and Webcast 49

Posted by timothy
from the checklist-for-recruiters dept.
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."
This discussion has been archived. No new comments can be posted.

2009 ACM Programming Contest Results and Webcast

Comments Filter:
  • 6 continents? (Score:2, Informative)

    by cwebster (100824)

    Last time I checked there were 7.

  • by Itninja (937614)
    There's this cool place down South called Antarctica. People even work there: http://en.wikipedia.org/wiki/Demographics_of_Antarctica [wikipedia.org]
  • Commentary (Score:4, Funny)

    by KingPin27 (1290730) on Wednesday April 22, 2009 @02:52PM (#27677465)
    "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: (Score:3, Informative)

      by Mad Merlin (837387)

      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.

      • by piojo (995934)

        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 (Score:3, Informative)

    by MrEricSir (398214) on Wednesday April 22, 2009 @03:25PM (#27677815) Homepage

    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)

      by -kertrats- (718219) on Wednesday April 22, 2009 @03:39PM (#27677983) Journal
      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 (Score:4, Informative)

        by kristoferkarlsson (621051) on Wednesday April 22, 2009 @03:57PM (#27678233)

        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)

        by MrEricSir (398214)

        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.

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

      by Keyper7 (1160079) on Wednesday April 22, 2009 @05:13PM (#27679283)

      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.

      • 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

      • 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

    • 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

A method of solution is perfect if we can forsee from the start, and even prove, that following that method we shall attain our aim. -- Leibnitz

Working...