Stories
Slash Boxes
Comments
Search

News for nerds, stuff that matters

Slashdot Log In

Log In

Create Account  |  Retrieve Password

2006 ACM Programming Contest Complete

Posted by ScuttleMonkey on Wed Apr 12, 2006 06:01 PM
from the all-wrappered-up dept.
Programming IT Technology
prostoalex writes "World finals for 2006 ACM programming contest took place in San Antonio, TX this year, and the results are in. Russia's Saratov State University solved 5 contest problems in record time, followed closely by Altai State Technical University (Russia) with 5 problems solved as well. University of Twente (Netherlands), Shanghai Jiao Tong University (China), Warsaw University (Poland), St. Petersburg State University (Russia), Massachusetts Institute of Technology (USA), Moscow State University (Russia), University of Waterloo (Canada) and Jagiellonian University - Krakow (Poland) all completed 4 problems."
+ -
story

Related Stories

[+] 2007 ACM Contest Winners Announced 110 comments
prostoalex writes "2007 ACM International Collegiate Programming Contest is over with Warsaw University (Poland) winning it this year and solving all of the problems. The runner-up, Tsinghua University (China), finished with 7 problems solved, while St. Petersburg University of IT, Mechanics and Optics (Russia) and MIT (USA) are tied up for the third place with 6 problems solved. There were 6000 teams initially in the running, and in the final round of the competition only 88 remained."
This discussion has been archived. No new comments can be posted.
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.

2006 ACM Programming Contest Complete 50 Comments More /

 Full
 Abbreviated
 Hidden
More
Loading... please wait.

  • GO USA!!!!!!! (Score:4, Funny)

    by Anonymous Coward on Wednesday April 12 2006, @06:04PM (#15117420)
    Woohoooooooo! Wait a minute...
      • Whoa, I can't believe you had the nerve to say that stuff. Didn't you know its currently the height of fashion to hate the USA? Guaranteed to get you modded down.

  • In retaliation (Score:5, Funny)

    by Snarfangel (203258) on Wednesday April 12 2006, @06:09PM (#15117450) Homepage
    ...MIT stole Saratov State University's cannon.
    • > ...MIT stole Saratov State University's cannon.

      In California, CalTech had to go to Soviet Russia, only to be stolen by what was once their own cannon?

      "...what a canonical meme!"
      - Slashdov Smirnov

  • Not final scores... (Score:5, Interesting)

    by qbproger (467459) on Wednesday April 12 2006, @06:15PM (#15117476) Homepage
    As someone who has their school at the competition, and I'm on the programming team (though my team didn't make it this year). Those are the scores as of one hour left in the competition.

    They don't update the scores during the last hour to keep suspence for the awards ceremony. So this isn't really news at all, and the post is going to be meaningless as soon as they update the standings. I'm expecting them to be posted soon though as I think the awards ceremony ended recently.

  • One Question & A Short Rant (Score:5, Interesting)

    by hyfe (641811) on Wednesday April 12 2006, @06:24PM (#15117522)
    1. Anybody managed to find the actual test questions?
    It's always interesting to see how advanced these are. Most of the time, I'm really not impressed by the complexity of the assignments, although the optimalization work done by the teams can be pretty 'way-better-than-anything-I-could-ever-do".

    2. If you ever see Russian State Universities at the top of anything, be very, very cautious. I studied at MGU (Moscow State University) for a little while, and it was frankly appaling. They were taught extremely specific skillsets, they knew exactly what they would be tested in in advance of tests and didn't study *anything* else. It was like a game of 'getting through Uni without learning *anything*' which outranked anything I've ever seen back home (or heard of in the US). The methology probably lends itself well to predefined, known tests, but it produces practically useless students.

    (To be fair, here back home, the ones who really learn something are the ones with a real interest in the subject, and they learn most of it outside class. There were really bright people at MGU too. It was the mindnumbingly staggering uselessness of the average student there which amazed me. It was supposed to be a "Top University".. oh, and you had to bring your own toiletpaper if you wanted to take a dump :)

    • 1. Anybody managed to find the actual test questions?

      Among the puzzlers, greatly simplified here: Write a program that computes how the gears of a clock can be connected with an hour and a minute hand, based on a provided input shaft speed with a maximum of three gears per shaft. Create a program that can find the maximum numbers of degrees of separation for a network of people. Develop a system to interconnect different nodes of a corporate network in the cheapest possible way.

    • 1. Anybody managed to find the actual test questions?

      It looks like you will be able to get them in pdf from from the contest website [baylor.edu]. (As of the time of this posting, the link hasn't gone live.)

    • Re:One Question & A Short Rant (Score:5, Interesting)

      by arrrrg (902404) on Wednesday April 12 2006, @07:13PM (#15117767)
      It's always interesting to see how advanced these are. Most of the time, I'm really not impressed by the complexity of the assignments, although the optimalization work done by the teams can be pretty 'way-better-than-anything-I-could-ever-do".

      You must be talking about another contest, on crack, or a super-genius (I won't hazard a guess as to which). I was on the Berkeley ACM team this year, and the International-level problems are HARD ... unless by "complexity" you mean the difficulty of writing a guess-and-check "solution" (which will be exponentially too slow). Usually, coming up with an algorithm with good asymptotic time complexity is the focus, and is very difficult. Almost all of them are not ones you can look at and just say "oh, that's max flow", etc, unlike some of the regional contest problems. And, from my experience at least, optimization is not that important at all. If you get the right algorithm, the problems can typically be solved in well under the time limit without doing anything fancy. If you do the naive thing, no amount of constant-factor optimization will allow the thing to finish before the universe ends. Just my $.02 ... don't take my word for it though, look at last year's problems and see what you think: http://cii-judge.baylor.edu/ [baylor.edu]

      • Re:One Question & A Short Rant (Score:5, Informative)

        by jbf (30261) on Wednesday April 12 2006, @07:33PM (#15117889)
        As a member of the second place team in world finals many moons ago, I have to disagree. I think the problems are actually quite simple algorithmically, and that the hard part is quickly writing working code for semicomplicated problems (including input parsing) with only one computer shared three ways.

        • As a two-time contestant at finals myself, I'll split the difference between the two of you. Both times I went the problem set contained a fairly even mix:

          1. Problems with obvious good solution algorithms that were easy to code (and everyone got these)

          2. Problems that took careful inspect to find a non-exponential brute-force algorithm that were easy to code once you figured this out. (Most teams got these towards the end of the contest)

          3. Problems with fairly obvious solutions that were challenging t

      • If you get the right algorithm, the problems can typically be solved in well under the time limit without doing anything fancy. If you do the naive thing, no amount of constant-factor optimization will allow the thing to finish before the universe ends.

        Well, to be frank; if you're reasonably not-stupid, finding an algorithm that scales well shouldn't be a problem (alot of people seem to be reasonably stupid though.. a lot of people who really ought to know better). Sure, it'll take time, and actually impl

      • Urg, first reply missed my closing statement to parent.

        In the end, I guess I, just like everybody else, am impressed by stuff I'm bad at, while the stuff I actually have talent won't seem as magical. Sure people are better than me, but they're not *that* better.

    • They were taught extremely specific skillsets, they knew exactly what they would be tested in in advance of tests and didn't study *anything* else. It was like a game of 'getting through Uni without learning *anything*' which outranked anything I've ever seen back home

      That description sounds a lot like MIT. I felt bad for the Aero/Astro kids asking us for electrical help. Sure we all got B's on it, but...that was like a couple months ago.

    • Appaling (Score:4, Interesting)

      by melted (227442) on Wednesday April 12 2006, @09:19PM (#15118382) Homepage
      Yeah, dude, I know why it was "appaling". Because you couldn't handle studying there, that's why. Compared to education in the US, the situation in Russian higher education is completely the opposite of what you've described. Folks are being taught extremely broadly, perhaps with too little attention paid to practical applications of what is taught at times. And you can't narrow down the scope of your education because you _can't_ choose classes. You fucking WILL learn linear algebra, physics, differential calculus, discrete mathematics, etc., whether you like it or not.

      It is expected of students to be able to figure out practical applications on their own. MGU in particular is one of the most hardcore Russian schools that is easily on par with _any_ Western college or university for which here in the US you'd be paying _through the nose_. MGU seems to be specifically designed to produce scientists and researchers, not engineers, though. MIFI, MAI, MSTU and NGU on the other hand focus on generating engineers that get shit done. The reason being, they produce most of Russia's engineers who work on weapons and high tech.
      • Yeah, dude, I know why it was "appaling". Because you couldn't handle studying there, that's why.

        Moscow didn't impress me no.

        You fucking WILL learn linear algebra, physics, differential calculus, discrete mathematics, etc., whether you like it or not.

        I know Linear Algebra, Differential Calculus, Discrete mathematics.. Physics is a weak spot though (relativly, took the courses, got bad grades and deserved them).. I finished my Master Thesis in Computer Science. Seriously, I know my shit. I met some re

    • If you ever see Russian State Universities at the top of anything, be very, very cautious. I studied at MGU (Moscow State University) for a little while, and it was frankly appaling. They were taught extremely specific skillsets, they knew exactly what they would be tested in in advance of tests and didn't study *anything* else.

      This is a highly spot-on comment. The problem ACM is now discovering, I suspect, is that in certain countries students at certain universities will work all year to compete in th

    • Re:One Question & A Short Rant (Score:4, Funny)

      by BMazurek (137285) on Wednesday April 12 2006, @09:55PM (#15118520)
      I studied at MGU (Moscow State University) for a little while\

      As a geek that moved to Moscow recently...were you ever able to find a bookstore that sold computer books in English?

      Please!?

      • The large Dom Knigi on Novy Arbat, (right next to the Norwegian Embassy if you have a tourist guide, I might be mistaking the streetname), had the largest selection of English book I could find. Never checked out computer books though.
      • Agreed, my post really was borderline trolling. Article wasn't about the state of Russian Universities.

        Well, the fact that you seem to be thinking my first language is English is a tribute to our Education System :). Optimalization was a direct translation of 'Optimalisering' which is the Norwegian word.

  • I need a piece of software in 10 minutes?!?!? (Score:5, Insightful)

    by shadowen1977 (903138) on Wednesday April 12 2006, @06:29PM (#15117549)
    I like this quote from the story.... "When was the last time you heard someone say 'I need a piece of software in 10 minutes?" Ask my boss.... He needs it in 5.
  • Is that the winning Russian univeristies are in very provincial places. Saratov is in the middle of nowhere East of the Volga River and Altai is actually in Kazakhstan.

  • Online ACM problems (Score:5, Informative)

    by BinaryOpty (736955) on Wednesday April 12 2006, @07:05PM (#15117720)
    For those who want to know more about this contest in the form of actually attempting ACM questions, then I suggest heading over to their problemset archive [online-judge.uva.es] which not only has ACM stuff from the last 5 years but a large number of non-ACM programming problems in the same vein. You can sign up with them and have your solutions to their problems checked for correctness.

    Since the website's a design massacre, to get to the ACM problems you need to click on the link marked THE CII ICPC LIVE ARCHIVE !!! [acmicpc-li...ive.uva.es] in the news bar, or just click on that one right there.

  • Waterloo! (Score:5, Funny)

    by mrtroy (640746) on Wednesday April 12 2006, @07:37PM (#15117901)
    Here is a picture of our library taken during this exam period

    Library [imageshack.us]
     
  • I remember my only entrance into the ACM programming contest. It was the first round of competition. We felt pretty good going in (calling ourselves team "Kwik Fill" after the gas station we stopped at along the way). We were the cream of the crop of the state school we attended.

    The first bump in the road was the compiler on the VAX. "Couldn't it have been a Sparc, or at least a Mac?", I thought, as we spent the first hour of the competition trying to understand how to get the compiler to work. You might as
    • All in all, it was a good performance. IIRC, we tied for 4th, as one team scored 4 points, two scored 3 points, one scored 2 and we were tied with the other eight teams with 1/2 point.

      Wouldn't you have been tied for fifth?
  • This is how it's done.

    http://www.ludumdare.com/ [ludumdare.com]

    Creativity, cunning, coding and caffine.
     

  • Actual results (Score:5, Informative)

    by insaneparadox (600390) on Wednesday April 12 2006, @08:38PM (#15118193)
    As noted previously, the mentioned scores were from an hour before the contest's end. My sources give the actual, final medal results as the following:

    1. Saratov State University (Russia) - 6 problems
    2. Jagiellonian University - Krakow (Poland) - 6 problems
    3. Altai State Technical University (Russia) - 5 problems
    4. University of Twente (Netherlands) - 5 problems
    5. Shanghai Jiao Tong University (China) - 5 problems
    6. St. Petersburg State University (Russia) - 5 problems
    7. Warsaw University (Poland) - 5 problems
    8. Massachusetts Institute of Technology (USA) - 5 problems
    9. Moscow State University (Russia) - 5 problems
    10. Ufa State Technical University (Russia) - 5 problems
    11. University of Alberta (Canada) - 4 problems
    12. University of Waterloo (Canada) - 4 problems

    Four teams each received gold, silver, and bronze (in the above order). For the same number of problems, the order is based on penalty minutes.
      • Newswires are wrong. I have the printed standings in front of me.

        The top 4 (Saratov, Jagiellonian, Altai, Twente) got gold, the
        next 4 silver, the next 4 bronze.

        Gordon Cormack
        Coach, Waterloo

        P.S. Please do lobby ICPC to be more spectator-friendly.
        Although they seem to care about the profile of the
        contest, they seem indifferent to advertising
        and reporting on-line results. They refused to disclose
        a scoreboard link in advance; the actual contest time
        was not well advertised; even after the start of the
        contest
  • When I was in high school I participated in the ACSL [acsl.org] (American Computer Science League) contest among high schools which still is running. It seems similar, they had a written test on computer science related things and a series of practical team programming problems. It was a blast when our team beat the champion (we were Montclair Kimberly, I think it was the 82-83 contest). Seems like the ACM contest has more interesting and difficult problems, looks like knowledge of genetic algorithms and simulated

  • Experience with incompetent judges... (Score:4, Interesting)

    by LoveMe2Times (416048) on Wednesday April 12 2006, @09:54PM (#15118512) Homepage Journal
    I am still angry to this day. The "judges" had the wrong answer to one of the problems. Of course, it was the problem that I took for my group. I had it right the first time, within a few minutes. Submit, wrong, time penalty. Hmmm... futz with it a little, submit, wrong, penalty, repeat. In the end, my team came in like third or fourth, due to these penalties. Turns out, the teams that came in ahead of us hadn't even submitted any answers for that problem. Of course, nobody in the competition got it right, and only one other team submitted an answer, I think. What *really* pissed me off, though, is that our fucking school administrators refused to take up the fight on our behalf to have the results changed. If we had hadn't had the penalties, I think we would have been 2nd, and if we'd been credited for the correct answer, we would have come in first. Either way, we would've gone to the next round or whatever. I don't know if this was standard everywhere or not, but they passed out the "official" answers when it was over, so we discovered how we'd been cheated on the way home, and it was trivial to verify that their answer was wrong.

    However, I must agree with some of the other posters: it's not so much a programming competition. It's more of an algorithms and standard library memorization competition. I seem to recall that knowing *all* the ins and outs of the printf family of functions was pretty important. Looking at the site now, it looks like they provide docs for the standard libraries, I don't think this was the case where I went. Anyway, it's important that you know that Java has a regular expression parser as part of the std lib (and therefore usable in the contest) while C++ doesn't. In real life, if you need a regular expression parser, you go get one. Additionally, looking at last years problems, for example, one of them is a straightforward application of a shortest-path algorithm. Do I remember the inner workings of the common graph algorithms? No, I don't use them very often. But I have my reference book handy if I need it. 99% of the time, I'll just use boost::graph. That problem could be solved quite trivially in 20 minutes with boost::graph. If you want to test my knowledge of graph algorithms, that's fine. My algorithms textbook has many exercises which do just that. Just don't call it a programming test. Everything in my algo class was pen and paper. In fact, if you're a real progammer, and you didn't use boost::graph (or something similar) to solve that problem, you deserve to be fired. Writing your own from scratch is a horrible waste of time and a maintenance nightmare. In fact, the boost libraries probably trivialize a number of ACM problems, what with graph libraries, matrix libraries, parsing frameworks, regular expressions, state machines, and so forth. A programming contest would force you to use these well, not re-write them.
  • I'm glad that Polish universities had a good showing. I grew up there and was educated there and always thought that CS education in Poland was top notch quality. Much better than in the UK for example, where I also studied for a while.

  • Sore Losers, really sore losers (Score:3, Interesting)

    by theolein (316044) on Thursday April 13 2006, @05:58AM (#15119745) Journal
    I am not surprised but still kind of irritated that almost all of the comments here revolve around either rationalising away the fact that no american team was at the top or being directly insulting of foreign universities.

    You americans are a bunch of wet nappies. You take a fucking programming and problem solving contest personally even though none of you were actually there. Not only that but you take it personally on a national level, as if your patriotic pride were somehow damaged because of this.

    America is a country that has lots of strengths, such as competitiveness, but also lots of weaknesses. such as an almost total inability to lose with grace.

    Maybe it's a good thing that (you americans)(sic) lost this competition.
    • You should have a look at the ICFP contest then: http://icfpcontest.org/ [icfpcontest.org].
      No prefabricated problems.
      More time to do the job.
      Any programming language.
      ...

    • Re:Ugh not again... (Score:5, Insightful)

      by Tammuz (320333) on Wednesday April 12 2006, @06:48PM (#15117624)
      It's generally unfair to judge ACM teams by the polish of their answers, since the only criteria is to solve the problem in minimum time. Similarly, problems are chosen with the time-constraint in mind, not out of any attempt to further science. If you want that, try the MCM [comap.com].

      What's impressive about the winning solutions is that they went from having nothing to implementing a working program from scratch, under stress in only a few minutes. While that is arguably not applicable to being a programmer in real-life, just as being an Olympic sprinter doesn't prepare you for any particular job, it is certainly a commendable intellectual achievement.

      • Re:Ugh not again... (Score:2, Insightful)

        by Anonymous Coward
        What you're missing is how hard the problems are, hard as in "math" not as in "complicated, annoying specs". Time is only used as a tiebreaker, how many problems you solve is what matters most. In fact most teams spend much longer wasting terminal time on flawed algorithms than they do typing up problems they have solved - in other words, if you know how to do a problem, there is plenty of time to implement it. (Teams that know how to solve lots of problems might run into time issues, but this rarely affect

    • Re:Ugh not again... (Score:4, Insightful)

      by Expert Determination (950523) on Wednesday April 12 2006, @06:51PM (#15117645)
      It's no *programming* contest at all. It's much more like an algorithm-solving+text formatting race. They don't test your REAL programming skills - your ability to create your own programming libraries, the organization of your source code, the maintainability, etc.
      Oh please! That's like saying the Olympics aren't a real contest because they only test the prowess of athletes, not their ability to tidy up the locker room after use, their politeness towards other clients at the gym or how nice their outfits look on TV.
      • That was a funny one. Anyway, I can say this: Most of the people in here who are programmers have stumbled upon spaghetti code. Well, I have. The guy who wrote that was seen as a genius because he managed to build a full database catalog (where you edit all the records in a DB table) in only 15 minutes.

        Wow, that's cool, isn't it?

        Well, those 15 minutes turned into several hours of maintenance. (He used copy/paste a lot, now try to adjust 20 similar spaghetti php+html+sql pages - no, no templates - when you

        • And conversely... (Score:5, Insightful)

          by Expert Determination (950523) on Wednesday April 12 2006, @07:26PM (#15117839)
          ...I've spent too much time in companies where people write nice, neat, tidy, well documented and easy to maintain code, but nobody actually knows how to do anything other than plumb one API into another. Every so often I'd come across a tool that someone had written that actually did something and I'd be bemused. How the hell did this lot write that? And I'd dig down through the source code and eventually find that under the mountain of wrappers and delegators and empty architecture there was actually a nugget, like V'ger [wikipedia.org], that did real work. And someone would explain to me "that's the code that Joe wrote years ago, he left and now we daren't touch that stuff, we just maintain the wrappers".

          The truth is that you need both kind of people in software companies. And the other truth is that the people who write the nuggets do interesting work that is worthy of displaying publicly in a contest. And the rest do work that isn't.

          Having said that, plumbing competitions [pmmag.com] aren't completely unheard of.

        • Speed is probably the most visible aspect of ACM programming contests, but really correctness is the most important criterion. The scoring system gives you 0 points for something that passes 95% of the tests, and the feedback is not much more informative than yes/no.

          My own experience is three years of regional contests and two at Worlds. The usual allowed languages are C++ and Java.

          In the first year I wrote essentially in the C subset, although I did sometimes make declarations in the middle of a bloc

      • Re:Ugh not again... (Score:4, Insightful)

        by GlassHeart (579618) on Wednesday April 12 2006, @07:24PM (#15117825) Journal
        That's like saying the Olympics aren't a real contest because they only test the prowess of athletes, not their ability to tidy up the locker room after use, their politeness towards other clients at the gym or how nice their outfits look on TV.

        No, that's like saying the Olympics isn't a real contest of athletics because you're only testing how fast they can run 100 meters. The results don't show who was fastest at 10 meters, 50 meters, or who would be fastest at 150 or 1,000 meters. Recognizing this shortcoming, the Decathlon adds up the scores from multiple events to find the best all-around track and field athlete.

        A programming contest is the equivalent of a single track and field event. There's nothing wrong with that, but we have to be careful what conclusions we draw from its results.

      • Not sure that is the right analogy.. it'd be more like if the olympics had one event: the 100 meter dash. That is exactly what this competition is, a single event race, it's only measure is speed of completion. Of course it is hard to evaluate less tangibles like maintainabilty and ease of reuse.

        My proposal: make programming competitions more like figure skating, where you get points on different aspects from a variety of judges. Might make a interesting tv show even (probably not in all honesty).
    • It's no *programming* contest at all. It's much more like an algorithm-solving+text formatting race. They don't test your REAL programming skills - your ability to create your own programming libraries, the organization of your source code, the maintainability, etc.

      You're right. Real programmers rarely bother with formatting...

      (No, I'm not kidding...I make my money testing their stuff -- don't knock test programming, it's some of the purest computer hacking there is -- and I make about half of it because t

    • Re:Ugh not again... (Score:4, Insightful)

      by schnitzi (243781) on Wednesday April 12 2006, @07:23PM (#15117822) Homepage
      Your rant sounds like an angry ex post facto rationalization for losing.

      I've spent many years involved in ACM programming contests, as a competitor, coach, and judge. And let me tell you, every team that considers it a hacking contest, and treats it like a hacking contest, LOSES. The teams that write well organized code, with simple straightforward solutions, win the day every time.

      I'm not surprised you did poorly.

      BTW, of course they compare output files. Would you really expect the judges to give an aesthetic judgment of each program in a five hour contest? "9.8 from the Russian judge..."
      • It is a hacking contest to quite some extent. Unlike most programming contests I've taken part in, coding skills have far more importance than the ability to come with the best algorithm in O(n) sense.

        An example: in my time (1998), we didn't whack our teammate upside the head for doing one of the tasks the real way instead of just going for the naive algorithm. The naive one was O(n^3), the optimal one -- O(n), but max n was... 100. In our national competitions and on most exams done by folks from our fa
      • I guess that depends on what you mean by hacking. In my experience, often it's raw coding speed that carries the day, and having lots of tricks at your disposal helps enormously. But that will only get you so far without an ability to suss out the clever, concise solutions quickly. In any case, I agree with your "sour grapes" assessment of the parent.

        - Bob Hearn, member, Rice 1986 (3rd place) & 1987 ACM programming teams
    • I've participatedin the ACM local competitions for two years in a row now. If studying computer science has taught me anything, it's that understanding algorithms and design patterns is paramount. We should, in fact, have them memorized, and the competition reflects that.

      We all write programs, so we're all programmers, but I definitely think there is a difference between a "computer scientist" and, say, a computer engineer, a code monkey, a web programmer, etc.

      The ACM competition is computer science--no

    • Umm. the contest is about computer science so algorithm solving ability is exactly what needs to be tested, not how pretty your commenting is.

    • For many, it's like any sporting event -- just with lines of computer code instead of balls

      Was this sporting event in prison!? Lines of balls ... vivid!

All trademarks and copyrights on this page are owned by their respective owners. Comments are owned by the Poster. The Rest © 1997-2009 Geeknet, Inc.