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
It the Soviet Russia the competition solves You!
my endian is bigger than yours!
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.
guess you guys are not so tough anymore?
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
1 St Petersburg Institute of Fine Mechanics and Optics 7 1204
2 KTH - Royal Institute of Technology 6 1118
3 Belarusian State University 6 1157
4 Perm State University 6 1255
5 Massachusetts Institute of Technology 6 1312
6 National Taiwan University 5 773
7 California Institute of Technology 5 818
8 Izhevsk State Technical University 5 930
9 Harvard University 5 937
10 Warsaw University 5 938
11 ZhongShan (Sun Yat-sen) University 5 954
12 Queen's University 5 965
13 Shanghai Jiaotong University 5
13 Stanford University 5
15 Fudan University 4
15 Korea Advanced Institute of Science and Technology 4
15 Kyrgyz-Russian Slavic University 4
15 Nizhny Novgorod State University 4
15 Seoul National University 4
15 Universitat Politecnica de Catalunya 4
15 University of British Columbia 4
15 University of Calgary 4
15 University of Cape Town 4
15 University of New South Wales 4
15 University of Waterloo 4
15 Zhejiang University 4
27 Albert Einstein University Ulm 3
27 Amirkabir University of Technology 3
27 Bangladesh University of Engineering & Technology 3
27 Charles University Prague 3
27 Donghua University 3
27 Jagiellonian University - Krakow 3
27 Nanyang Technological University 3
27 Norwegian University of Science and Technology 3
27 Novosibirsk State University 3
27 Petrozavodsk State University 3
27 St. Petersburg State University 3
27 Tokyo Institute of Technology 3
27 University of Michigan - Ann Arbor 3
27 University of Otago 3
27 University of Tartu 3
27 University of Texas at Austin 3
27 Yonsei University 3
I'd like to see the solution for those.
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.
actually translated thats:
university of information technology, mechanics, and optics
If you don't like competition, then don't participate. Simple as that. Nobody's shoving it down your throat. Stupid illiterate.
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.
Kill Carl
If you can read this sig - the bitch fell off.
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.
Always remember :
"Premature Optimization is the Root of All Evil"
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.
Where are all the Indian universities? Some Indians say IIT is as good as MIT...
All the former Soviet block countries, (Russia - St. Peterberg University, Poland - Warsaw University) did best ..followed by US institutions,.. ahem
And u thaught u had'em beat.
I blame George W. for sending a wave of negative accademic karma, thus destabilising engineering colleges all over America.
...while Americans are dumb, incompetent, lazy, fat, ignorant and arrogant which qualifies them to manage all russians, indians, chinese and taiwanese combined...
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
Interesting alternative view of Stanford:
http://www.epinions.com/content_73675148932
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.
The average indian IQ is preety low according to international tests and this software contest confirms it. The very best indian colleges the IITs couldnt even get 3 out of 7 right! Even Bangladesh scored higher than them.
What does that tell you?
Why ban the most productive languages?
I think the real issue is that the Indian institutions don't really have any strong comp sci programs. It's an issue of (a) number of programs (there are few), (b) quality of programs (so-so, staffing is a huge concern), (c) number of students (too few) and (d) funding (hardly any).
Most of those "software engineers" you see at Infosys, TCS, Wipro, Satyam et al are engineering graduates (mechanical, chemical, electrical, etc), who get plucked by the companies and then trained by them in programming. But I'd hazard a guess that their training in fundamental data structures, analysis of algorithms and systems architecture is pretty weak.
So they learn on the job.
Intelligence isn't the issue, it's the combination of that and education.
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.
When I competed in the ACM competitions (a long, long time ago), FORTRAN was the only language we were allowed to use. We had to use the file editor running on the host school's computer. No books, no notes, no nothing, no prewritten code, nothing. Only one person in the terminal and only on person at the terminal at a time. No subroutnes, no functions, just straightforward code.
How much has changed since those days?
"If you want to program, you program for it's own sake"
"it's" = "it is"
"its" = possessive.
with all of the previous messages focusing on language proficiency, we consistently have people who post at a second grade level. Fortunately, it's not a measure of IQ, but a measure of mental organizational ability. And that isn't a good thing in the world of computers.
How about if we give you a broom instead?
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.