Slashdot Mirror
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)."
More outsourcing to come in areas more sophisticated than in codemonkeydom.
CC.
TaijiQuan (Huang, 5 loosenings)
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?
The contest is in virus form. If you have Internet Explorer, you will find the winners on your machine any time now. It's great that the whole world will be able to participate in this contest.
Don't blame Durga. I voted for Centauri.
You'll find that to be the case with most CS depts. You'll need to study law if you want to screw people.
Lack of Mt. Dew puts US programers at a serious disadvantage.
The world is made by those who show up for the job.
This doesn't really mean anything by itself. However, it's worth mentioning that the individual attitude is different in the rest of the world than it is in the U.S. (For example, the students at the Shanghai U. might be a bit more motivated to prove their talents than the students in the U.S. thanks to some social doctrines going around in the region).
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).
Whence? Hence. Whither? Thither.
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.
Don't blame Durga. I voted for Centauri.
The complete list of problems can be found here, along with some sample inputs/outputs (usual format for these types of contest).
The finals problem set (PDF) is at the finals home page.
Why? Because it didn't place a team in a coding competition? I wouldn't judge a countries technical ability based on something as abstract as this.
I havent read the article due to slashdotting but something like a programming competition seems very odd. I'm not sure how you could objectively measure something like this, and even if you could; as a programmer I can say that the most important quality to have is imagination or innovation, not the ability to sling the technically best code.
Top 10 Reasons To Procrastinate
10.
Glad to see "Canada's Top Math and CS University" is pulling in good results overseas too. ;)
Expectations are for the unprepared.
Mediocre programming is perhaps a labour job but I would take one brilliant programmer over five mediocre ones.
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.
http://icpc.baylor.edu/icpc/Finals/Scoreboard/inde x.html
...Communist (or ex) countries produce better programmers. Maybe it's because once you've tried commanding a whole economy, programming seems trivial by comparison.
This is not the sig you are looking for...
One of the Michigan Tech. team members was none other than Joe Nievelt one of the RIAA's "best friends"
These competitions seem to be very academic. Do they relate to programming in the real world? Although I applaud the people who won, I don't think that these are the right kind of competitions to be training people for. They should have a real open source design competition, where contestants are graded on the outcome of a large project. Extra points could be given for showing good use of testing, as well as good documentation and coding. You could also look at the use of special algorithms developed, but don't base all the points on this. There's more to programming these days than fancy algorithms.
Anthropic principle: We see the universe the way it is because if it were different we would not be here to see it.
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?
Gosh, thanks. That must be why the other ships call me Meatfucker -- GCU Grey Area (Eccentric)
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).
"reality has a well-known liberal bias" - Steven Colbert
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.
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 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.
"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. I was on the American University team, AU One)
OddManIn: A Game of guns and game theory.
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
Okay, a bit of explaining here. At the ACM you don't come up with fancy solutions printed on a piece of paper, you *implement* them. Your source code needs to pass a set of tests and is given a very limited amount of time for each one of them. In most cases you need to optimize your code a lot (and by this I mean use the best algorithms possible). You submit your code, it gets evaluated automatically and you get a message like "OK", "Error", "Bad format", "Core dump" -- I don't remember exactly all the names, it's been a few years since I participated at an ACM World Finals (Vancouver, 2001). After that you wonder what the heck went wrong (just like in real word, I may add), you modify it, you submit it again and so on. Of course, penalties add up for multiple submissions for the same problem.
DFM (Design for Manufacturing) -- yes, you are correct. But ACM and the other international contests prepare you exactly for that.
--B
According to the official scoreboard the top 3 are Moscow, St. Petersburg and Waterloo (all ranked with same amount of solved questions). Shanghai placed 4th, but they're the champions?
I'm sorry and I don't want to sound like a troll, but judging from your post it seems to me that you don't know jack shit about programming or those contests.
:)
Yes, there are some mental challenges in programming, but for most part, it's straight forward (especially object based programming)
Those are not straightforward programming contests, they're algorithmic oriented contests.
here are real geniouses out there that can code in assembler, etc, but for most part, coding is like any other labor job.
It doesn't take any genius in special to code in assembly. In fact, most assembly programming is hard work but doesn't require any special brain to do it, compared with programming in other languages (I'm not talking about comparing idiots who only know java and the like).
If programming is so easy, I dare you participate in some programming contests similar to the one being discussed in this topic. Keep us updated on the results later
The AACS key is NOT 0xF606EEFD628B1CA427BEA93A9CA9773F
And who are you to decide time is the most important factor in good programming? I would say the team with the cleanest and best documented code should win.
Linux is not Windows
No kidding. The grandparent should be moderated troll. Before accusing someone he know nothing about of cheating, perhaps he could have check the past results and see that this school (along with all the other leaders) has performed very well at every contest in recent history, including winning the 2002 contest in Honolulu, Hawaii. Or maybe the US coordinators were in a conspiricy againt the US teams as well.
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.
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... 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.
Now it is about 6-9 questions and you have 5 hours to solve them. Code is submitted using the PC^2 system.
Are you sure your cable didn't go through the planet? ;-)
Just kidding. The judges sound like mid-level management candidates.
You are in a maze of twisty little passages, all alike.
. In my own experience, at Oklahoma State University the ACM is virtually non-existant. I served as PR Officer in my last semester, and I think we had 4 meetings. Besides the officers, only a handful of people attended the regular meetings, and the only reason anyone signed up to be a member was because we stopped charging a local chapter membership fee. I don't think any local chapter members got a national membership. Our faculty and staff were not at all envolved in the ACM. There are also fewer and fewer students getting into programming these days - if anyone touches a computer field they go after business comm or MIS, because of the lure of better cash without having to learn so much math and science. So I point the finger at envolvement. In my experience, there was not enough envolvement by the students or faculty to get a team of competitive, motivated programmers to represent our school. I'm curious as to whether other schools in the US have the same problems.
perl -e "eval pack(q{H*},join q{},qw{70 72696e74207061636b28717b482a7d2c717b343 637323635363534323533343430617d293b})"
Not really. I was an assistant coach for my school's team in 1998 and had a long discussion with the department chair about this.
Basically, with the rules that are in place from the school and the board of regents for the state colleges, there isn't a lot of incentives that can be given to students to participate in something like this. I talked with a member of the Waterloo team and they were getting a couple of class credits for being on the team, which is something our school couldn't give. It wasn't considered appropriate - should we then give credits to someone in athletic studies for being a member of a school athletic team? Another issue (back in 1998) was that most US students didn't need the line on their resume, or the job offer from IBM if they won the contest. (Note: The job offer from IBM to the winning team was anecdotal, but IBM seemed interested in talking to everyone there about job opportunities.) Also, the "good students" don't participate in these contests since most of them have some sort of programming job on the side. I talked to several people about being on the team and they told me they would rather go to work and make US$20-30/hr being a part-time programmer than practicing for a contest.
Just my US$0.02
Reading code is like reading the dictionary - you have to read half of it before you can go back and understand it.
I wasn't offended at all. It's pretty clear that people hate the implication that their country isn't better then all the others on the basis of an earth shattering result in a programming contest. Just as I was tickled pink to see Waterloo in the top 4. However no matter how good our programming is in Canada - we just don't have the military forces to arbitrarily invade countries on flimsy pretexts - so they can whip it out, measure and feel better.
The rock, the vulture, and the chain
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.
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.
That's what seperated the teams that attended (all of which are excellent) from the teams that won.
:) Some day, when you aren't paying attention though we'll get you. Some day. Or maybe I should just go to canada when I finally decide to go back to grad school :)
I can't speak for MIT or the other teams that went, but I have participated in the regional contests several times before, and for us it was something that we did in our spare time. Our only preperation was three local contests through-out the year and at most a couple days before each contest practicing problems. I'm sure that the US teams going to internationals a lot spend more time than that, but I don't think it even compares to the asian teams.
The asian schools take a great deal of pride in winning this contest and they have dedicated teams that spent tons of time working on this event. It is almost the same as if they were representing their country in the olympics. In fact that's a perfect analogy. Like this contest, the olympics have little direct practical application - how does jumping over a really tall pole make you a better worker in any job? The point of the contest is to simply performance for the sake of performance - to challenge yourself to the end of your abilities and prove that you can be the best in the world. This is a cultural attitude that the US doesn't really have in academics. The people here that are good in engineering are pragmatists that want to get a job done, and look at these contests as a fun diversion, not a matter of national dignity.
PS, our school seems doomed to place 3rd or 4th every year, foiled by those pesky canadians yet again
And I'm not hostile to Islam -- I once shouted "Allahu akbar!" during rush hour at the intersection of Lawrence and Homestead. (I admit, mainly because I thought it was a subversive act.)
Seastead this.
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.
You can see past winners here: http://icpc.baylor.edu/past/default.htm
The ACM problem sets. I don't know when the current problems get added, but all the old ones, plus more, are on this site. You can write the program, then submit it to their online judge to see if it's correct.
Brute force usually doesn't work, so you need to know the right algorithm. It's tough, but it's fun!
Ardente veritate incendite tenebras mundi
Technically if you lose at anything it's because you were at a disadvantage, even if that disadvantage was apathy or being thick as pigshit.
Strength through redundancy and over-design
I'm American, and love my country, but we have to face facts. U.S. society doesn't place a lot of value on academic knowledge, compared to the rest of the world. Our cultural heroes aren't scientists, academics, and thinkers -- they are entertainers and athletes. We respect practicality, and making money, not intellectual understanding. Our society has a longstanding democratic suspicion of elites, including intellectual elites, which often shows up as a disdain for 'impractical' academics. There are several examples of this cultural disdain in the responses to this topic (taking the form of, "who cares, it has no relevance to the practical realm of real-world programming/software engineering."
You can argue about whether or not this disdain for intellectual mastery is good, but the U.S. is one of the few countries in the world where the theory of evolution isn't widely accepted. Perhaps our culture's disdain for and mistrust of elites has a real price, and this contest is one place it shows up? Perhaps it also encourages many of the brightest students to go into areas where they can make money -- law, medical, or business school -- rather than academia?
Because historically the U.S. has has a better economy. Those 'pesky foreigners' get a lesser education in the US than they would at home because 1. The competition for 'top of the class' is a lot easier and 2. American companies can pronounce the name of the American university, whereas they cannot pronounce the name of the foreign university. They instantly (and incorrectly) suspect the foreign school as being sub-standard, and refuse to hire the person from the 'foreign country and foreign university'. I had a prof. in university who came from China. He had an engineering degree from a school of radio engineering in China. No one would touch him, so he got a PhD from the University of Chicago/Urbanna Champaigne. It was a breeze. Now everyone wants him.
Of course, even something this simple can have problems. At the Fall 2004 Mid-Central(IL, MO, etc) competition, the judging software was set up incorrectly so that it compared your resulting output to... your resulting output. The only way to fail was for a program to not compile or to run too long(i.e. get stuck in an inf loop), so at the very end of the contest one of the teams picked up on this after submitting something they knew shouldn't have worked, and solved the "hard problem" by outputting the completely nonsensical string "everybody wang chung tonight".
The solution to the problem however, due to the fact that by the time the judges realized this the contest was over, was to simply re-judge all the entries correctly, meaning that the only way to get a problem right in the end was to have been 100% correct in the first place(whereas normally you could resubmit the program if it was outputting the wrong data, taking a time penalty). As a result, I don't have much faith in the mid-central results this year, or even the whole of NA for that matter(there's just no way to know who really belonged at the finals from mid-central); and more importantly it shows while file comparisons can be a very bad idea.
Why do so many international students struggle to enter the best American universities
There is a lot of high-level research in the US, and big budgets for research.
Why do they leave their country to come to [...] be taught by stupid American professors?
Many professors are not American either, or were not when they first came.
How can American high schools be so much worse than European ones, but still produce students that go to the same universities?
There are brilliant people everywhere. The difference of education shows mainly with average and sub-average people.
Compare it with food in different countries. There are great restaurants in just about any country (if you can afford them). But there are not many countries where you can walk into some random restaurant around the corner and have a good chance of being served decent food. Of the countries I know, I would count Italy, Lebanon, Marocco and Thailand as the ones with good food.
I am not bashing Americans and saying the whole country is worse and those "great" foreigners are all better. It just happens that science, sadly, is not a strong point in the American education.
Secondary education is different, while high schools are fairly uniform, colleges are very different from each other -- some are really good, some average, some should just stick to basket weaving.
Sometime colleges compensate for the high school's shortcomings. Freshmen usually are required to take a math series in the first year, if they manage to step up and pass, they'll be ok, if not, basket weaving or plumbing is highly encouraged as an alternative career choice.
I just think, from what I have experienced, that high school science here is watered down. The kids are encouraged to run around chase a ball or play the trumpet, while they can't read or write. Teachers don't dare make the "poor" students feel stupid so they water the stuff down. In my high school back home in Russia I had to spend the whole time outside the classes doing homework and only then if I had time, do extracurricular activities. If most people failed the test they just got bad grades and that's it. (Note: that encourages some frequent cheating, a bad problem in that neck of the woods) The few of the ones that managed to do well and studied all the stuff are much better and end up coming to this country usually to teach and learn from the other people just like them from all over the world, while at the same time doing a ton of research for this country.
To summarize, I think the science program in US high schools is simplified and dumbed down to cater to the below average student, at the expense of depriving the better students of a good and thorough science curriculum.
Jiao Tong are "host" only insofar as they laid out a great welcome mat for the world. The facilities were excellent and they showed us Chinese acrobats and a just-for-us fireworks show that rivals any I've seen.
ACM ICPC is an American organization, and they have complete control over the judging. IBM supplied the hardware and the ICPC staff supplied the software and judging staff.
In the last hour, any of the 4 gold medallists could have won. Waterloo submitted problem A but didn't get it. The Russian teams submitted problem G but didn't get it. Jiao Tong overcame a 1-problem deficit and then, with about 10 minutes to go, solved problem D to win.
Have a look at the problems and you can decide for yourself whether or not they catered to any particular audience. I think not.
I congratulate Jiao Tong and thank them for their hospitality.
Gordon Cormack
coach,
Waterloo
No Waterloo student receives a class credit for participating in the ACM contest. They get the occasional free pizza and trips to exotic lands. That's it.
Gordon Cormack
coach
Waterloo
"Sometimes, it's an institutional thing, as noted by postings to this article about certain countries offering entire courses centered around this competition."
F /
Like these ones, for instance:
http://www.cse.unr.edu/~westphal/spring2005/cs491
http://www.cs.sunysb.edu/~skiena/392/
http://www.cs.berkeley.edu/~hilfingr/csx98/
http://www.cs.hmc.edu/~dodds/ACM/homeACM.html