29th ACM Intl. Programming Contest Results

mathinator writes "The 29th ACM International Collegiate Programming Contest World Finals, hosted by China's Shanghai Jiao Tong University, are now over and the results are in. Congratulations to the top 4 teams who will be walking away with gold medals. They are Shanghai Jiao Tong University, Moscow State University, St. Petersburg Institute of Optics and Mechanics, and Canada's University of Waterloo (coming in at 1, 2, 3, 4 respectively. The top 4 get gold medals). Regional champions are: University of Waterloo, Canada (North America); Moscow State University, Russia (Europe); University of Cape Town, South Africa, (Africa and the Middle East); Instituto Tecnologico de Aeronautica, Brazil (Latin America); Shanghai Jiaotong University, China (Asia); and University of New South Wales, Australia (South Pacific)."

Wow, no US teams placed!

[HeelToe (615905)]

Not sure if it's surprising or not.

Is it the lack of quality programs these days or lack of interest on the part of highly talented students to participate?

Re:Wow, no US teams placed!

[joshdick (619079)]

You shouldn't judge programmers of CS curricula based on these competitions. The problems are all very academic in nature rather than practical (I've competed in the ACM for two years now). Also, some schools spend all year preparing for the competition, offering classes in it, whereas other schools don't put quite that much into it.

Furthermore, the results of a single competition is hardly any reason to pass judgement on CS students nationwide.

Re:Wow, no US teams placed!

[rbarreira (836272)]

I mostly agree with what you say, but I think those contests are partly a good indicator of how good a programmer is. There are 2/3 components which are necessary to win a competition like this:

- Knowing how to program fast and flawlessly
- Knowing a lot of data structures, and knowning how to choose the right one for a problem (mainly trees, tries, hash tables, vectors, linked lists, graphs and ocasionally special data structures for geometrical data)
- Knowing how to solve some classical problems, mainly in dynamic programming and graphs, where a lot of problems are used again and again in those contests (though with variations or presented in an obsfucated way).

I'd say that the first two are indicators of knowing how to program well. The third one is more discussible, since there are a lot of schools which prepare their contestants to know those algorithms by heart... I'm not saying they don't understand them, but that component alone doesn't show much ability to me :)

Re:Wow, no US teams placed!

[drgonzo59 (747139)]

It's like with any test. If you pass, the first thing it shows is that you can do _that_ particular test well. Of course the reason for the test is to show that you are knowledgeble in the whole domain that the test was compiled from, but that is a speculation. You are right, I can spend the whole year, doing nothing but learning all the algorithms that might show up on the exam, and practice to solve a common set of problem fast, sothen I migth do well on that contest, but I might still not do well in general in college or workplace.

That said, I also happen to be from Russia, and I can say that in general education system there is more thorough and more focused on the science than here in US (I went to schools in US too). Here all schools seem to be doing is try to make students comfortable, they have a hundreds of clubs and activities for after school. Everyone and their little brother wants to play sports or play in the band first then study. Schools try to be fun, instead of trying to make student learn something usefull. I remember coming to this country and doing my sophomore grade in fairly good high school, but I had to take calculus with the graduating seniors and I remember tutoring them in math even though I was an average student at home in that subject.

No Mountain Dew

[jbeaupre (752124)]

Lack of Mt. Dew puts US programers at a serious disadvantage.

Re:Wow, no US teams placed!

[wviperw (706068)]

Actually, this is the INTERNATIONAL Collegiate Programming Contest. The way it works is that each country is split up into regions. The first round consists of regionals and the qualifiers move to the final round where they compete against the top teams from other countries. So, in a sense, this *was* a US-based competition for the first round.

Look pretty realistic to me

[CaymanIslandCarpedie (868408)]

To begin, no I didn't attend any of the places mentioned in this article so I'm not biased.

Now the host placing first may seem a bit suspicious, but the other universities in the top four certainly lend some credibility to it.

I've worked with a number of russion developers which have come from those universities and they were quite brilliant. It seems they actually teach math and physics there, what a concept! ;-)

I personally rate the University of Waterloo (in Canada) the top computer science university in North America. Yes high profile places like MIT have some brilliant people, but I've found the University of Waterloo has the most consistant quality of graduates. If you look at the accomplishments of Waterloo grads it pretty impressive. Research In Motion (Blackberries) are probably the most well known company founded by UofW grads, but there are lots of others which are also very impressive. Thier policy on requiring LOTS of real world experience for the degree and work/research opportunities in there technology park also gives lots of great experiance.

I've found UofW grads aren't those "fresh out of college" types who have some book knowledge, but not much practical experience. They tend to walk out after graduating ready to REALLY contribute instead of needing a lot of "mentoring" which most fresh grads need (I know I did).

Woo Waterloo!!

[taneem (873769)]

I'm a Waterloo student and it's awesome to see how we did. Waterloo competes regularly and has had a winning place several times before.

As for the people who have been insinuating that the Shanghai Jiao Tong University rigged the results, take a look [baylor.edu] at the past winners page. They were the winners in 2002 as well (hosted in Honolulu).

As for the actual problem set: it can be found (PDF)here [baylor.edu].

I competed once...

[bdbolton (830677)]

I participated in the southern regional ACM programming contest. GaTech won with Florida coming in second. The questions are extremely hard. We solved one problem. They give you 5 lines of test data but when the judges test it they will use hundreds of lines of test data. Not only must your program be correct it must also be fast (less than 3 minutes)

oh and honorable mention means you didn't solve any. Take that Tech! ;)

-Brian

What surprises me

[Stevyn (691306)]

I looked at the questions and I was surprised they didn't include some basic computer skills. No where did they ask how to install an operating system. Compiling a kernel wasn't mentioned. Configuring a license server? Nope! MySQL? Not a damn reference.

It's obvious to me that these "computer scientists" aren't skilled for the real world and will never get a respectable IT job.

Poor poor USA

[Spankophile (78098)]

So they didn't place.

Now all I see is people saying: "The Contest isn't representative", "The Metrics are poor", "The problems are academic", and "I wouldn't judge the state of CS curricula based on a contest"

That's all find and good - as long as you sleep better tonight.

But you still didn't place.

Re:Wow im amazed

[j0e_average (611151)]

Ironicly, they dn't offer SE[x] on main campus.

You'll find that to be the case with most CS depts. You'll need to study law if you want to screw people.

Re:Funny stuff about this contest...

[kahei (466208)]

So well let's assume this is a fair test of programming skill, why is it that an Islamic state's team, Sharif University of Technology, beat out not only the top technical university of India (IIT) but all of the US's Ivy League schools -- not just MIT and CalTech?

Hmm, maybe they solved more problems in less time.

(The above is of course just a theory. It could be a global conspiracy against America).

List of problems

[LordFoo (518001)]

The complete list of problems can be found here [baylor.edu], along with some sample inputs/outputs (usual format for these types of contest).

Finals Problem Set

[mparaz (31980)]

The finals problem set [baylor.edu] (PDF) is at the finals home page [baylor.edu].

Re:Funny stuff about this contest...

[ari_j (90255)]

It's not anywhere near fair. Our ACM chapter competed a few years ago. We didn't make it past the first round on account of getting one problem "wrong." By "wrong," of course, I mean that we produced a better solution than the judges had, and some other teams produced the same, non-optimal solution that they had, so we were wrong. I later sent in a detailed proof of our answer's correctness as the unique optimal solution, but we never heard back.

For what it's worth, that problem was "Given a list of latitude and longitude points on the surface of Mars, which has radius R, what is the minimum total length of cable needed to connect those points to form a network, if the cable is 1m above the planet's surface? Assume that Mars is spherical."

To this day, I have no idea what the "correct" answer was that took several hundred more meters of cable than our solution did.

Re:Funny stuff about this contest...

[0xABADC0DA (867955)]

Maybe they put one point at 0,0 and you got a divide by zero error? ACM put in all kinds of test data like that which is to any sane person completely impossible for the given question. When I was in the regionals a LONG time ago the ACM actually rescored one of the problems after the contest was over, adding extra test data so another team's problem would pass but ours would not (there was a conflict with the rules and apparently they thought it was easier to just cheat). We were hosting that one which is the only reason we found out.

Overall I don't put much stock in the results because it's really more of a contest about robotic perfectionism. Unlike what people might expect there is extremely little creativity or problem-solving involved; each team has huge books of problems that they laboriously solve over and over again and there are never any fundamentally new problems in the competitions. I mean not like they could come up with an entirely new type of problem for each questions, but they always follow the same pattern: each problem has 1 fundamental approach you have to use (dynamic programming, graph-coloring, pattern-matching, monte-carlo) and then it's solved. Combine that with not telling any clues about why the program failed and it's really geared towards more robotic programmers. I got out of it precisely because there was virtually no creativity or thinking involved at all, at the professional level.

Also it's virtually impossible to detect cheating... if you watch these people, they basically start coding right from the start anyway so if you already knew the problem and solution there would be little difference to see, it would just look like that team was really good. Or maybe you see test data, or somebody elbows you and says 'be sure to check for 0,0 on the mars problem'.

A much better approach was done on topcode.com [topcoder.com]... there you get to see the test data and why your program failed. Then afterwards other contestants get to look at your code for a while and purposely try to break it with their own (valid) test cases. And you get bonus points for breaking other people's programs.

Re:Funny stuff about this contest...

[erikkemperman (252014)]

let's assume this is a fair test of programming skill, why is it that an Islamic state's team, Sharif University of Technology, beat out not only the top technical university of India (IIT) but all of the US's Ivy League schools -- not just MIT and CalTech

I sure hope I misunderstood you there: do you mean to suggest that "a fair test of programming skill" could not possibly have a winner from an Islamic state? Just so we're clear on this, I don't know whether this competition is fair or not (other posters seem to think not) but why would religion have anything to do with it?

Re:Funny stuff about this contest...

[johannesg (664142)]

So well let's assume this is a fair test of programming skill, why is it that an Islamic state's team, Sharif University of Technology, beat out not only the top technical university of India (IIT) but all of the US's Ivy League schools -- not just MIT and CalTech?

One reason I can think of is because they really are better now. Don't forget, there hasn't been any good reason to study computer science in the US for a while now, unless you _enjoy_ flipping burgers of course. On the other hand, the countries to which all that work is outsourced have a strong need to produce more and more competent programmers. The result is a loss of competence in the US, in favor of those other countries.

Not so sad?

[AtariAmarok (451306)]

If you look at the "Top 4", you will see that the region groupings only allows one winner from North America. A Canadian college got this one, but there are US schools in the results list of runner ups.

Re:Not so sad?

[sk8king (573108)]

Canadian University. Waterloo is THE post-secondary institution for math and computer science in Canada. Or at least that is my impression of it.

Re:Not a single U.S. school

[Washizu (220337)]

"I'm not sure how you could objectively measure something like this"

I did the competition in 2001 when I was in college. It may be slightly different now, but back then each team of 3 students got 9 problems and an hour to code solutions on one machine. You submitted your code to a server and it compiled it and ran it against unknown input and output (we knew the parameters, but not the actual input). Success/failure notices, or compilation errors were quickly IM'd back to you.

The team is scored using this criteria
1. Number of problems solved
2. The total time taken before submitting correct answers + any penalty minutes for submitting incorrect or incompilable code.

So a team who got 9 questions right in a half hour would score better than a team who got 9 right in 45 minutes.

(As for how we did, we were able to solve 4/9 questions and tied for 17th place. Results here [baylor.edu]. I was on the American University team, AU One)

Re:Individual Efforts

[corvair2k1 (658439)]

This is very much an effort based on the teams themselves. The cream of the crop is picked from the school's department, and they train/practice for months. If you were to lift any other student and send them off to competition, the lack of preparation would make them noncompetitors. These competitions exercise one very specific programming skill: Dash off a program that can do this impressive thing (with not much real-world applicability) as fast as possible, as a team. Real-world situations never call for this sort of programming, so these people are truly drilling for this type of event.

Re:Coding is blue collar

[teslar (706653)]

Coding, in my humble opinion, is akin to any other blue collar vocation. Like coal mining or any other labor job. Yes, there are some mental challenges in programming, but for most part, it's straight forward (especially object based programming).

If programming is like coal mining, can you do a PhD in Coal Mining too?

You, sir, seem to misunderstand what programming is about. Programming is not jotting down some if statements, for loops and the like - any 9 year old can do that after having reading a bit through Learn C++ in 21 days and in the development cycle of a program, it is probably the least time-intensive part.
But defining the problem you're tackling, designing your solution, your strategy, your algorithms, indeed the program itself (and yes, this includes the OO Paradigm - you don't seriously think the OO Paradigm is a funky thing where everything just works automagically with zip effort?) takes up at least half the total development time and it is not "some mental challenge with most part labour", it is purely a mental challenge. The most important tools of a programmer are a pencil and (lots of) paper. After the design is finished, you spend another significant amount of time deciding how to best implement your design. And yes, all of this is important and this is what they teach CS students at universities - or did you think it was all about different ways of writing a while loop? The better your design, the less time you will spend debugging your program (another substantial part of the development cycle of a program and another purely mental task once you've ironed out the compiler errors due to typos).

So don't diss it till you've done it - you clearly haven't.

Re:no US team has ever placed

[lars (72)]

That is definitely not true. The contest didn't start to become very international until recently (the last 10 years or so), so prior to that US teams won most of the time. The last time a US team won was in 1997, but they've placed well since then (e.g. MIT was 2nd in 2002).

You can see past winners here: http://icpc.baylor.edu/past/default.htm [baylor.edu]