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
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.
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
1703-1914: Saint-Petersburg (or Sankt-Petersburg in German)
1914-1924: Petrograd
1924-1991: Leningrad
1991-....: Saint-Petersburg
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.
I can't say.
People just liked it better that way
I can't imagine this would be a surprise to anyone, considering that nearly every russian programmer I've met was awesome... of course, perhaps it's because they were "awesome" that they are in the USA now!
stuff |
A fine performance by KTH from Sweden. By the way, where is the Chalmers team? ;-)
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.
Not that the problems were tough to figure out how to solve. It was more implementing of what mainly was a bunch of geometry problems takes real long in comparison to most other types.
You may have been modded Flamebait, but I think thats pretty damn funny. I guess the mods don't get the joke in the last sentence...
Athletic Scholarships to universities make as much sense as academic scholarships to sports teams.
I empathise with your predicament.
We had a similar thing happen to us in the pre-Regionals round (a model solution was wrong!). However, the judges subsequently recognised the problem and allowed us into the regionals (in the days before the South Pacific had its own region) -- which we won (end of 1990). Ahhh, the good old days...
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.
I wonder if many of the international teams appreciated some of the subtle humor in these problem sets, especially this. =)
-Cyc
/.'s 10 Millionth
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.
This is a selfless post I guess you could say. But I would just like to use this time to conrgradulate my friends that I see every day. While many of you may think South Dakota is still cowboys and Native Americans. The School of Mines and Technology programming teams represent!
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.
Try (print (fact -1)).
Or (print (fact 1.5)).
Or (print (fact "Hi, Mom!")).
In a dynamically-typed language like LISP, it is important to check that the argument(s) is(are) of the right type, as well as within the proper range(s).
So you should add a check to make sure that the arg to fact is a positive integer.
To avoid doing this check every time that the function recurses, fact should do the check, then hand off the calc to a helper function, say, unchecked-fact, that is defined similar to the way that you originally defined fact.
Those who sacrifice security to condemn liberty deserve to repeat history or something. - Benjamin Santayana
I thought that sounded like a strange name for a school in Florida that I never heard of.
Higher score is worse. Score is a measure of the time it took to complete the problems.
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.
BTW:
Both definitions of factorial (recursive and non-recursive) are perfectly good (mathematically) ways of defining the function. However, in the Real World, there's a large difference: even in lazy languages, allocating the space for the list (stream? generator? i'm not very well-versed in Haskell) is going to take memory and computing time. In fact, i think that in this particular (trivial) example, allocation will take as much if not more resources than generating the data itself. The recursive definition, on the other hand, does not present this problem, since the numbers are generated on-the-fly (and the function is tail recursive).
So, while defining factorial as the multiplication of a list might be very elegant, it's not extremely efficient (in both languages that are lazy like Haskell and those that aren't like, say, Lisp), since data is generated and then immediately thrown away. The recursive function remains elegant while not being wasteful. In fact, a compiler that recognizes tail-recursion should make it as efficient as the iterative version.
Try Corewar @ www.koth.org - rec.games.corewar
The U.S., on the other hand, has a lower average (in my experience), but a *much* wider distribution. You find many more true stars as a percentage of grads.
Why doesn't that generate wins in the ACM contest, you might ask? Well, at least when I looked into joining my school's team, it was a very informal thing. No studying and practicing for years, no serious coaches, etc. That's changed somewhat, but these *are* the kinds of problems that get easier the more you practice them.
Having looked at quite a few, I can pick out an ACM question in seconds... they're really unique. Oh, and completely unrelated to anything anyone actually does in the real world :-). I'm not saying that's necessarily a bad thing.
I participated in the contest in 1992, with our NYU team winning the NY regional and placing 12th in the finals. The most memorable aspect of this contest for me was the emphasis on teamwork. Even twelve years ago, there was only one machine. It is obvious to everyone, by now, that there is only one computer in the entire world, albeit with some nodes as yet unconnected. Cooperation is still the key to progress in our field.
By the way, I was the only "American" on our team, and that made it much more fun. Everyone should know that nationality has no bearing on programming ability. Moreover, international group events can serve as a partial cure for racial prejudice.
The problems aren't overly tough, but you are given seven or eight of them to solve in just five hours. It's the time crunch that makes it hard. Anyone can get a right solution eventually, but how many can you belt out as fast as possible - that's the challenge. The contest is designed so that even the winning team doesn't have the time to get all of the problems right.
In general, it's a lot of fun. As I stated elsewhere here, the one time I tried it there was a mistake in the givens that made things unfair, but in general it's a fun idea. They just need to be a lot more careful with their problem handouts. Perhaps they should do some trial runs with test students first before using the problems for real.
Don't label something "offtopic" unless you know the topic well enough to tell what's on topic.
They still limit the team to only one computer for all of them (the theory is that this allows poorer installations, that can't afford a spot for everyone, to participate fairly - also it forces the team members to 'talk offline' about solutions while one is frantically typing code. (Each team is given a private room near the computer lab, to run off to and make plans and come back.) Actually, they defineded 'terminal' as a single installation of keyboard and screen, regardless of whether it's a standalone PC or a terminal.
They don't do fortran anymore, but they do specify the language. Back when I did it (10 years ago), they said you had to do either C or Pascal. Today it's probably going to include Java, but I don't know that for sure. languages that tend to do a lot of data structure work for you, like lisp, were not allowed.
They allowed us to bring books and notes, but in paper form only - no stuff that could be transferred electronically.
Don't label something "offtopic" unless you know the topic well enough to tell what's on topic.
You are right about software engineering, that is where they still show some weaknesses, but no more than the Indians.
The end result is that you get what you pay for. If you are prepared to spend time supervising projects on a personal basis, they will work. and work well.