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
I competed in the Northwest-European finals but didn't make it to the world finals. The problems looked pretty difficult.
I, for one welcome our new russian fiberoptic programming overlords.
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.
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.
If anyone knows more about what happened to MIT, I would be interested to know. MIT's score is higher than the other competitors so I wonder which of the problems they struggled on.
ayottesoftware.com
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 agree! Last year two friends and I competed in the local, and regional competitions, but didn't go any further than that. It was a blast.
Plus, having two second-year compsci guys and a first-year engineer come in and beat everyone (including the profs, althought they were writting in Eiffel I think), was pretty funny. Mind you, we only won by a few points.
When we got to regionals though, it was clear that we didn't have the experience needed to go further. We had 8 hours I believe, and sadly, a few of those were fighting with stupid language problems, instead of actually solving problems. As an example, for one of the problems, we ended up overflowing a double in C, because the data was too big. The solution? Rebuild the same problem in Java, using a BigInt...
All in all, it was a great time, and since we finished first locally, the CMPT department paid for us to go to regionals.
Comment removed based on user account deletion
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.
Looking at these results, it would seem that outsourcing to Russia or Taiwan, or keep jobs here, would be more sensible. The IITs only got honorable mention. Is it simply the money?
I didn't think the house band in Hell would play this badly.
I was at NWERC '03 in Lund and one of the problems (the one with the train system) had a badly formed input but since our team assumed at the input was formatted correctly (which was guaranteed by the problem spec.) our program crashed. We got it right on the first try but we spent a lot of time looking for buggy code and searching for reasons to crash.
We wasted lots of time and didn't complete any more problems but we were close to solve a problem in the last few minutes so we may have gotten two problems solved instead of one if the spec had been correct.
Interestingly enough, the team that won (and came second in the world finals (congrats to Threeheaded monkey!)) had the same problem but also deduced that the input was flawed so they notified the judges. I suppose we would have gotten zero problems solved if it hadn't been for them.
The difference between our stories is that we wouldn't have chance at the top 10 anyway.
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.