Slashdot Mirror
2006 ACM Programming Contest Complete
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."
Woohoooooooo! Wait a minute...
I already said why the ACM programming contest is crap, I won't say it again.
...MIT stole Saratov State University's cannon.
This tagline is copyrighted material. Please send $10 for an affordable replacement.
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.
- Joe
... this bullshit has absolutely nothing to do with programming. These are more or less general problems that needn't involve computers at all - just get a paper and a pencil. It is imho absolutely not demanding to code a problem that has a simple (read: already proven stem) outside CS.
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 :)
"" How about taking the safety labels off everything, and let the stupidity-problem solve itself? """
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.
... the contest wins you!
In Soviet Russia, problems solve you (in record time too!!!!)
I got nothin'
From TFA:
For many, it's like any sporting event -- just with lines of computer code instead of balls
That seems really unprofessional and childish, even for a Yahoo story.
1) Your analysis is based on bad assumptions so your result is way off. 2) You're a sick bastard for fucking a horse.
At Russia's Saratov State University, contest problems solve YOU!!
Blessed are the 1337, for they shall pwn the earth.
Start queueing up the "In Soviet Russia" one liners...
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.
Facts do not cease to exist because they are ignored.
on redundant slashdot, soviet russia jokes post YOU!
I do not accept czechs.
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 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 !!! in the news bar, or just click on that one right there.
with the voices of a million cheers:
In Soviet Russia, Saratov State U!!!
Fuckin' GEEKS. Well someone had to say it.
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 aren't completely unheard of.
"The White House is not an intelligence-gathering agency," -- Scott McClellan, Whitehouse spokesman.
Actually, Adelaide came 37th.
We (the University of Otago) came 27th back in 2004 when I participated. Whatever others say about the contest, I loved it and certainly enjoyed the trip to Prague.
Wasn't this a competition of higher education? We didn't do all too hot.
"This is considered plagiarism."
Here is a picture of our library taken during this exam period
Library
[I can picture a world without war, without hate. I can picture us attacking that world, because they'd never expect it]
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 ask why we spent the first hour on the system and not working out algorithms to address the problems. To that, I answer: Have you seen those problems?
By now, the Dew buzz was wearing off. We almost got two programs working and took several pictures of us pretending to toss the VT220 terminal out the window before time expired.
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.
After that, I started focusing on networks. Ah, the good old days.
This is how it's done.
http://www.ludumdare.com/
Creativity, cunning, coding and caffine.
-- That which does not kill us has made its last mistake.
In Soviet Russia, the ACM wins you... oh wait!!
In the US, the ACM wins you!
(* US lost the ACM, so ACM won the US... get it? *)
-ItsME
It was a great time. The team I was on placed fourth at the competition (we would say "We're the fourth best team in the free world.") The Russians weren't participating then, though a team from Switzerland did. Along with a team from Israel if I remember right. When I was the alternate the team placed second - it's kinda depressing to know that the team did better without me :-(
I got mod points for my birthday :)
thanks slashdot.
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.
I thought they were supposed to be the new thing. What happened?
I haven't found info on what they had to program - I'd like to suggest to the rwth-aachen to participate next time, but I'd like to see what kinds of problems are to be solved (at least to know to which faculty I should suggest that... besides I'd be interested in that myself...)
The MAFIAA is a bunch of mindless jerks who will be the first up against the wall when the revolution comes
Here are the top twelve finishers. These are the real final results, not the ``suspense'' results from one hour before the contest finished.
Saratov State
Jageillonian U.
Altai State
Twente
Jiao Tong
St. Petersburg State
Warsaw
MIT
Moscow State
Ufa State
Alberta
Waterloo
When I was in high school I participated in the ACSL (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 annealing might even be useful! Looking forward to seeing the results (the programs) if they are published.
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.
Some may be interested in the IEEE design competition: http://www.computer.org/csidc, which typically involves designing a hardware/software system constrained within a pre-determined theme. Judging entries includes considering the creativity in addressing the theme, how well the design/development process was planned and executed, does the system work correctly, etc. Submissions are initially judged as paper designs. Those submissions that make the cut have working models judged.
I believe both contests have their merits.
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.
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?
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.
Your pizza just the way you ought to have it.
Why even bother going to MIT.
Seems like this is just another well, better than average university. People like flies get fooled into thinking that they get good education here, where in reality there are places more advanced and sophisticated.
And one more thing. Thank you guys from India and other countries for coming to MIT to get your Master and PhD. Otherwise it would become community college in no time.
Other programming challenges -- with useful results are sitting around all over the place that just need some more money to get the competition kickstarted.
Seastead this.
It seems that countries who's emotional eqivlency is null usually wins these types of contests. All of the programming tests I take with employers point in this direction. This seem that anyone who can express emotions aren't good programmers. One must seperate themselves to an objective state in which there is no feelings...only logic. It's the NCIS programs on CBS...no emotion, just logic. Kind'a like my relationship with my girlfriend...only she doesn't understand it.
Rusty Foster
Founder, Kuro5hin.org
MIT stole Saratov State University's cannon.
.. more likely S-300 or something
3.243F6A8885A308D313
"When was the last time you heard someone say 'I need a piece of software in 10 minutes?" - never. It's always like this: I need that code 10 minutes ago!
So 10 minutes after, we are already 20 minutes too late.
You can't handle the truth.
For the curious, another type of contest is http://www.challenge24.org/
You can bring your own computers, use as many as you want, bring any electronic or printed materials you want, use any language or libraries you want, and have 24 hours to crack down and solve a problem.
It's closer to the "real world" in that you can use any tool to solve the problem (solutions are graded, not code), and the time period removes the 'get it quick' mentality. It's unlike the "real world" in that you can't use the Internet (cheating reasons) and you aren't evaluated on maintainability, but that's a near impossible thing to evaluate objectively.
For what it's worth, any people I know personally that do well at these contests are usually what I would consider "smart" people and are people I wouldn't mind programming with. YMMV.
I think it's time to recognise the opportunity to automate this yearly rehash of the discussion around the ACM contest results. I don't even need to read all the posts, we've all seen it before!
:)
It's time to possibly consider new advances in natural language systems and auto-generate the slashdot discussion for coming years. Here are the key elements:
a. jokes made at the expense of the American teams (which is not necessarily even fair IMO; the problems are damn hard, and solving 4 while the Russians or Chinese solve 5, for example, does not imply a pending catastrophe in the American higher education system)
b. inevitable comparisons made between the budgets of the American vs. non-American universities
c. indignant responses from insecure B, C-class American developers who just don't get that computer science is rooted in mathematics, and complaining that the contest is not "realistic", probably since they've never seen the inside of a University
d. Waterloo students, sometimes being the only university in North America in the top 10, thumbing their noses at the American schools, and espousing the superiority of their school (disclaimer: I went to Waterloo)
e. Gloating from the {Russian, Chinese, other non-American} winners
f. Accusations from those same B, C class developers/students that students from {insert_winning_univ_here} are "specifically trained" to take the contest (yes, in fact they are: it's called being educated, and that's what is supposed to happen in a university, not frat parties)
There may be other general categories, or maybe i've missed a couple, but i think this fits most of the posts pretty nicely.
Here is my idea: take all discussions from previous ACM contests where the results are essentially the same, and use some automated or perhaps manual procedure to flag the post as one of the above categories. For example, the parent probably belongs in class "c" although that's not a perfect fit. Develop a relatively simple transition diagram or whatever to designate which type of post should follow another. Some examples, using the designations from above:
post "e" --> "f" or less likely "c" (say (0.8, 0.2) probability)
post "a" --> "c" or less likely "f" (again say (0.8, 0.2)
post "f" --> "b" or sometimes "d"
And so on...
Put together a relatively simple database of posts, do some random selection and assignment with the above and i'll bet you can generate a somewhat coherent discussion.
Perhaps this should be a problem in the 2007 ACM
For those who don't get the joke: I've repeatedly put the suggestion for the C-Prize up here at /. with the additional suggestion that the Google founders who are participating with the X-Prize committee do it. This means guys like Sergey Brin and Larry Page, both Jews AFAIK, would be responsible for choosing the administrators. Now, we all know there is an increasing appearance that neocons are supremacist and that they're largely Jews but -- you'll just have to trust me on this -- they aren't likely to give me a red cent out of it.
Seastead this.
It's not entirely impossible that the person who writes the nuggets also writes 'nice, neat, tidy, well documented and easy to maintain code', you know. Some programmers with a little more talent don't think they have to, because they think they're gods gift to the company, but I'd rather have a person writes maintainable code than a cowboy coder, because a cowboy coder needs to do even his own work all over every few years, because he can't remember WTF this algorithm does, and he hasn't the documentation to refresh his memory.
---
"The chances of a demonic possession spreading are remote -- relax."
I could see spending a semester on contest questions, instead of say... Compiler Design, would be a distinct advantage in
Category F.
Damn, I've been categorized. Please disregard my observation.
Those are my principles. If you don't like them I have others. -Groucho Marx
I write code for a living professionally. I agree this competition is far from useful. However I think we Americans are overlooking some relevant facts.
We're very fortunate in the United States. It's true that we do very badly on any sort of mean international measures of educational quality. Yet, how many foreign students would give their right arm to go to Caltech or MIT? Most Americans don't have to fight for a successful life. If you want a good job, it's clearly within your grasp. Heck, you get to reach for your dreams. How many kids in a third-world country get a chance at that? If you're born into the wrong caste in India, it can be a challenge just to get an education. (Incidentally, I find the caste system [which seems to be pretty rampant to me; however feel free to correct/enlighten (or the slashdot equivalent ?flame?) me on this] pretty abhorrent.)
Sure, most tests and competitions are garbage. You could argue the Putnam and mathematical olympiads are garbage too. Is it fair that some kids compete against other kids at schools that have classes to study for the Putnam? On the other hand, some previous winners include Irving Kaplansky and Richard Feynman.
If you want to talk about a test that doesn't accurately measure one's worth or ability.... Look at any of the GREs. Incidentally, I'm studying to take the Physics GRE. I do this because I want a chance at going to a good grad school. Sure, if I could afford to go to a better undergrad program, I would. In fact, my professors have suggested it. However, I can't and the GREs are my best shot at acceptance.
At one state university (a somewhat notable one) you can take classes to study for the Math GRE. While I'm not directly competing with those kids, I am competing with other kids who get professional preparation on the physics GRE. All I've got is a bunch of web sites and textbooks. How am I supposed to compete with this? Yet I will. I don't begrudge anyone trying their best to improve their chances for success in life.
Most of these kids in Russia (and other foreign countries) are dying for a chance to get noticed. What looks better on a CS grad school application to United States than winner ACM programming competition? Obviously good grades and research. However, I wouldn't be shocked if some these kids had that as well.
Whoever believes you can't train a genius is full of bunk. Is there any coincidence that Norbert Wiener's father was a linguistics professor at Harvard? How about Von Neumann's private tutors as a young boy? Don't you think those advantages in life make a difference? I for one congratulate everyone for their effort in the competition.
What do you mean my sig is repetitive? What do you mean my sig is repetitive? What do you mean....
The South Pacific region was very successful with two 1st places in the early 1990s:
- University of Otago, NZ, was the first non-US team to win in 1990
- Melbourne University won it for Australia in 1992
1992 was a particularly sweet victory. Stanford, the 1991 winner, was distraught at not winning and fled home before the final placings were announced. Not a particularly fine example of sportsmanship!
SS
P.S. Both the Otago and Melbourne victories owed a lot to Raewyn Boersen. Thanks Raewyn. We couldn't have done it without you!
Algorithms are just as important as the actual code itself.
Anyone can programme, its just a matter of learning syntax, and throwing the algorithm in that particular syntax, and voila, you end up with a widget/library/application.
Too many times I see programmers just jump straight into a programme, start pumping out code, then going, 'oh shit, I haven't considered.....' - it happens in opensource projects, especially in the lower levels of an application. The programmer not properly thinking out all the possibilities in which the library might need to cover, so the net result you have this library in a constant state of flux as things constantly need to get re-written, compatibility thrown out the window because nothing has actually been nailed down at each phase of the system development lifestyle; its just code getting throwing at problems, hoping something that will eventually stick.
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.
For some reason it shows standings about 2 hours prior to the end of the competition. In fact Jagellonians from Krakow were the 2nd, Altai was the 3rd.
http://flosspick.org finding the right open sour
Poor guy. I stopped going to regionals after a couple of times, (our CS department was cheap, so we had to share rooms and beds), but I think teaching some of the problems givin in the ACM is.. well, probably better for the student than just the regular class on Data structures and programming languages.
However, the problems I had were just a big bunch of text formatting (take this dictionary, check this sentence, blah blah blah), but then again I've not much faith in the southeast regionals anyway.
What I wouldn't give for them to combine my love of competition with my love of making games.
Well, besides these of course:
LD48
Pascal
Or did only 2 US schools rank in the top 51? (UCF Ranked 51st and I graduated from there,so I say top 51 :P )
I have had close friendships with students from the Moscow Institute of Physics and Technology and I will tell you that these guys ( unless related to Mafia barons ) work their rear ends off to really understand ( over even overstand ) the Subject in question. Their curricula reflects this. Others whom I have worked with and respected have been consistent in carrying their academic knowledge out of academia and are always critical in the design of every algorithm they ever touch. Don't you wonder why there are so many Russians in Google? A multi-tier interview process, filtering the best from around the world. Annoying gits.
These guys have the hearts of hackers, but the discipline of dedicated and passionate scientists ( not even just engineers ). That said, we should remember that it is bad to stereotype. :)
The reason American teams will probably never win is because American universities give their teams little to no support. The coach for Georgia Tech was an alumn that works in Atlanta, because no profs will do it. Any tenure track proffesor at a major CS school in America that takes time to coach a contest will not get tenure.
Contrast this to the Chinese team that won last year. The Chinese government bought the coach an SUV, in a country where most people don't have cars. Americans just don't care.
Oh, BTW, it was the 30th annual contest, not the 29th.
...one thing that is not of concern is input parsing. We had so much practice reading in any well-defined formats. The hard part is really finding the best algorithm that is asymptotically the best. Remember that your solution must compute not just a few sample questions. It will have to process 1000-1000000 test cases in under a few seconds and under certain memory limits. When you focus on the core algorithm and incorporate the scaffolding for input and into automation---you only need to focus on the algorithm and doing it correctly. The test cases the judges run during each submission test for all previously known 'base cases' and will ensure that any solution less than 100% perfect will fail. If you are interested in practicing ACM problems... please check out the Spanish ACM Archives. (http://acm.uva.es/ Pick a problem and submit it to the online judge and see how it is. The trick to a lot of these problems is the mathematics of the solution--not necessarily any 'computation'. Why compute something recursively, when there's a theorem that can provide the answer immediately? The problems are designed to capitalize on 'tricks' like this.
1992 was a particularly sweet victory. Stanford, the 1991 winner, was distraught at not winning and fled home before the final placings were announced. Not a particularly fine example of sportsmanship!
I find this story very hard to believe.
So Stanford decided to pike on all the remaining events, packed up their stuff, headed off to the airport and tried to get early tickets back to California... because they didn't win again? And it wasn't even the same bunch of guys on the team, it's not like they were defending their own title.
Add to that the fact that with the way the ACM works, if the final placings weren't announced yet, they couldn't know for sure they'd lost. And they'd give up receiving their 3rd place award? You're saying that 3rd was that unbearable? Have you ever seen an empty bronze spot on the podium at the olympics? And their coach was ok with all this?
Frankly I think there's either more to this story (they had to leave anyway for finals?) or in the past 14 years you've exaggerated it from "Stanford looked disappointed they lost" into this unbelievable whopper.
As for Russian CS educaton quality look at www.softpanorama.org. It billed itself something like Russian-speaking programmers society.
Pretty interesting site.
You can view the final standings here.
Below are the top twelve teams with their scores in bold and time penalty in brackets.
I took part this year as well as last year (African champions in both years) and one thing that I will point out is that this year's organisation was pretty shocking in comparison to last year. I'm sure many who were there last year will agree with me. It was just run so smoothly last year! I suppose it has a lot to do with the fact that it was in China and not in the states as it always is.
The Java Challenge was run especially badly with several fixes to the engine we had to interface with (and these were probelms with core features). And they changed a key rule an hour into the coding stages! Now that was just unecceptable. It changed he whole dynamics of the contest! My team won the challenge last year (Parrallel Challenge), but this year we stood no chance with the rule change, although we were doing very well before the change (score dropped from about 600 all the way down to 100!). And then the server crashed near the end and all submissions after its return were sent to an alternate directory - and they only picked this up long after, during the tournament in the evening! Shocking!!