Slashdot Mirror
ACM Collegiate Programming Contest Winner Announced
Slob Nerd writes "The finals for this years ACM International Collegiate Programming Contest World Finals have just finished. And the winner is... St. Petersburg Institute of Fine Mechanics and Optics! Full results here, and details on all teams here. A pdf of the problems is also available. Congrats to all involved."
St. Petersburg colleges always do well in these competitions, and all that happens is the people end up emigrating.
See my journal, I write things there
This championship looks very amateurish and unprofessional compared to this!
"A door is what a dog is perpetually on the wrong side of" - Ogden Nash
What is the appeal of turning everything into a competitive event? Whether its music, literature or programming, someone somewhere is trying to convert a self-contained creative process into a "Nyah, nyah, my college/school/town I'm better than deal."
What happened to the satisfaction of doing something for its own sake?
Athletic Scholarships to universities make as much sense as academic scholarships to sports teams.
Good job to all who participated. This thing is *hard* because, while the problems are not insurmountable, you are only give 5 hours to do as many of them as you can. It's a contest in how good you are at predicting where the difficulty in the problem lays, and nailing that problem right away. Some of the problems look deceptively simple. It's the ones that immediately notice what it is about them that's not simple that do well.
Way back when, I got to participate in one of these as an undergrad (it was 1994, if my memory is right). I've still got a little bit of a bitter memory over that one because a mistake in the givens of a problem caused our team to lose one of the problems - one which we would have gotten a HUGE score on otherwise. (Because it was done 'right'* in just 30 minutes, and your score is based on how much clock time was left after your solution is accepted.) (And that year the problems were really hard such that the winning team only got 3 of 7 done - they had accidentally given the undergrads the contest that was supposed to be for the grads - so missing one problem is a huge difference.)
* - But what was wrong with it was based entirely on a misprint in the problems presented to us. The problem involved calculating big factorial numbers (among a few other things). The trick was to realize that no computer had a native number format that could store 300 factorial, and so you had to invent your own string-of-digits number primative that could handle N digits and multiply two numbers - given that N could be in the thousands - it's a simple problem, but the trick is to realize it is necessary to make up your own primitive. I realized it right away and wrote up the number primitive in a few minutes. But there was a problem - the givens in the problem description guaranteed that the test input will contain no factorials that result in more than FOO digits, where FOO was something in th 5,000's. This was the misprint - the biggest test they used actually contained something like FOO+200 digits, where FOO was in the 5,000's. There was no good way to check this given, since to do so required that we have a large-number multiplying routine - which is what this program was all about in the first place - which is why they gave it to you as a given.
So when I allocated an array of size FOO+1 (for some overhead), my program kept crashing. Those people who got sloppy and didn't try to be efficient and just made a huge array of size 10,000 had their programs work just fine on the first attempt. Those people that tried believing the given in the problem had programs crashing. And the nature of the test environment was that we couldn't see our programs' responses to the test data, and the test results weren't allowed to tell us what really happened when the program was run - just that "program terminated prematurely.", and that's it - no information about the data that caused this, and no indication of where the program died. In our own tests everything worked fine because we weren't trying numbers larger than the givens PROMISED us the test data needed, but when the solution was submitted, the test data tried larger numbers than the given promised would be used, and thus the program crashed.
I only know what happened because an announcement was made 4 hours and 30 minutes into the contest that there was a misprint and then the correction was given. Then I changed the size of the array, resubmitted, and it was right, after too many penalty points for failed submissions, and 4 hours of points wasted on THEIR mistake. Yeah, I'm still a bit bitter, because their attitude was that the contest was allegedly still "fair" because everyone had the same misprint on their handouts, and scores would not be adjusted for this mistake. I called "bullshit" because some people hadn't even tried that problem and therefore were unaffected by its misprint, and people who had been sloppy and picked a huge array were also unaffected by the misprint.
Our team had a chance of pl
Don't label something "offtopic" unless you know the topic well enough to tell what's on topic.
Many slashdotters will probably be pleased to know that the contest's environment OS was Red Hat Linux 9.0.
Full environment specs here.
I hear there's rumors on the Slashdots
It comes as no surprise that Russian teams did especially well considering most of the problems relied heavily on mathematical understanding. It's perhaps the one country in the world where logic and math have been given their rightful place and respect in education.
Why do you assume that everyone else was "sloppy" and just allocated a big array? If you're going to write a big-int routine it's not that much more difficult to write an arbitrary precision routine than it is to write a "max FOO" precision routine.
I do think that they should have re-adjusted for the misprint, but it's pretty small of you to simply denigrate everyone else's performance. Perhaps they had been exposed to some other ways of working with large numbers than allocating arrays to the max precision. When I was in high school we had a pi calculator we used to run using DEC BASIC's arbitrary precision string arithmetic (this was before high-res graphics or we would probably have been wasting our time on fractals). I'm sure if I'd been given the problem I probably would have done something involving strings which probably would have worked.
One of the things I always liked about the ACM problems, both now and when I was competing, was that they were fun challenges. Very few "real world examples", instead they always made your head spin a few times and then you could dive right in.
You had a limited amount of time, and when I was going it only a single terminal so only one team member could actually code at once. So optimizing for time to code was a huge factor. But it also meant that you could afford to specialize a bit, have some out-of-the box thinkers who may be great algorethmically but not the best with real code, and a dedicated coder to implement.
I remember one year we had a Mechanical Engineer on the team who had a completely different approach. We were trying to work out how to do one problem correctly mathmatically and he mentioned that they only wanted two significant digits and suggested an iterative solution to the math problem that worked beautifully.
Hats off to all the competitors.
Cheers,
=Blue(23)
LITTLE GIRL: But which cookie will you eat FIRST? C. MONSTER: Me think you have misconception of cookie-eating process.
(I'm one of the Directors of the contest, so I know of what I speak.) "Score" is a terrible title. It should be "penalty". The teams are ranked first by the number of problems they got correct. Thus St. P's came in first, because they were the only team to get 7 problems correct. Among the four teams that got 6 problems correct, they are ranked from smallest penalty (KTH) to highest (MIT). Penalty is computed as the total cumulative time it takes you to solve a problem. So if you solve one problem after 30 minutes and a second problem after 30 additional minutes, your penalty is 90 minutes (30 from the first problem, 60 from the second). In addition, you are given 20 minutes of extra penalty for each incorrect submission to a problem that you eventually get correct.
Some posts already mention some reasons why this is a hard contest, but I thought I'd summarize and add a couple more:
* You have more problems than your team can possibly do in the time allotted. When I did it, the winners got 4 or 5 out of 8. There's a lot of pressure to work fast.
* All the problems are tricky, but there is definite variance in their difficulty. Since your score is based not only on how many you get right, but how fast you get them right, you have to figure out which problems are the easiest and do them first. Starting with a problem that looks easy but turns out not to be can really hose you.
* The answer evaluation is harsh. You submit a solution program and if it's not correct you get back a response like: "insufficient output", "too much output", or simply "incorrect output." Figuring out why the judges say your program doesn't work when you think it does can be really frustrating.
* There are multiple people on the team (4 my first time, 3 my second and I think since (but someone correct me if that's no the case)) and only one computer, so managing that resource is crucial.
I don't know how much the contest proves, or how much stock employers, say, should put in it, but it was fun to do.
I participated in this contest twice, in '96 and '97.
The first time, I was studying at a Bulgarian university (Sofia), and we scored 4th at the finals; MIT scored 5th. Two of us transfered to MIT that same year. Even though we had the skills to do well in such a contest (quick, efficient coding; algorithms knowledge; a little bit of teamwork), there's far more to computer science and engineering than that, and the rest is not taught in any Eastern European university.
And this is basically why programming contests are so hot in that part of the world. And why American students generally don't do well. It's all about the incentive! Kids in the US don't need to do it, and have little to gain. Whereas in Eastern Europe, it's the way to get some kind of recognition, and get on the fast track to a good education, a good job, etc. (Usually, involving immigrating, of course.)
Also, you should understand that these kids have been training for 5 years for such programming contests. Programming as a sport starts around 7 or 8th grade (IOI is the equivalent international contest for highschoolers), so by the time these kids get to college, they are highly experienced.
So, yeah, I expect the winners to apply to the best American universities and get in, of course.
MIT and Stanford can only gain by losing in that competition.