ACM World Final Standings Posted

Nyerp writes "The final results for the ACM International Collegiate Programming Contest are up. Cheers for St. Petersberg State U, followed by my own school, the Univerity of Waterloo!" Congratulations, guys! I wonder if any of the world finalists used Pascal, since it's allowed.

Cool. Another "place."

It's interesting how:

• Waterloo has been placing in the top six quite regularly, of late.
• No US institutions have been placing in the top 4, or, this year, in the top ten.

  Not MIT. Not CMU. None of the UC schools. Not Stanford.

The one non-apathetic thing I did in my time at UW was to help get teams heading back to the ACM Scholastic Programming Contest. That was quite a lot of work, and not terribly worthwhile at the time. It sure feels worthwhile now...

Prizes irrelevant...

If you're on a team that "places," you get a better prize than the possibility that IBM might give you a "free" laptop. You'll get:

Job Offers From Interesting Organizations.

Re:Controversy over Problem F

I was also present at the contest and did problem F. I heard this rumor as well, so I feel very lucky. I implemented the problem in a way that paths with "infinite" distances simply weren't counted when I obtained the average.

I've often wondered how these sorts of things should be resolved, and I don't really have any answer. I'd certainly be very angry if that were the case and I'd had to spend hours on the problem. I got lucky. (I just hope I do better next year).

logan

Re:Pascal

Delphi/Object Pascal is somewhat safer than C/C++ only because it is somewhat more limited in what or how you can use pointers. But that is a pretty marginal thing. You can certainly shoot yourself in the foot with pointers in either language. Whether it is faster or not is largely a matter of opinion, and which tool a given person is personally more comfortable with, and also which C/C++ tools are selected. To say 'a whole lot faster' is really not a fair generalization.

Probably my biggest complaint against Object Pascal/Delphi is that it is still mostly a uniplatform tool (albiet FreePascal and a couple of other free alternatives are in development, none are really finished and completely compatible with the Borland products yet). C/C++ multiplatform compatibility isn't perfect, far from it -- especially when moving code between Windows and and Linux/*nix/*BSD platforms. But at this point nontrivial C/C++ code that is written with the intention of being portable is much more likely to be so than any current Pascal dialect. There are also more 3rd party (free and commercial) products designed to work with C/C++ to aid in cross platform work than there are specifically tailored to any Pascal dialect. Much as some people deride it, few languages are as close to multiplatform as Java is at this point (not to say that Java is without problems either).

None of this may be that salient to the contest in question, but they certainly are things that often matter in the real world.

Pascal

Delphi is allowed. Which is really just Object Pascal with a nice gui maker. Anyway all of the teams I know who placed well at Regionals used pascal. It is simply safer, and a whole lot faster to develop with. I like C/C++ as much as the next guy, but use the right tool for the job.

Controversy over Problem F

I was on the CMU team. If you look at the statistics, you see that we solved 3 problems and were ranked 15th (in a tie). This is not what actually happened. We actually solved problem F correctly and did not get credit for it. At least a dozen other teams were also denied credit for a correct solution to this problem.

The controversy is that the judges and ACM contest staff still claim that there was no error in the grading of the problem, and that their datasets were consistent with the problem statement. Here's why I don't believe them.

Take a look at problem F. (Here are the contest problems [baylor.edu] in PDF if you're interested.) In a nutshell, you're given a complete directed graph, and you need to return the average length of all shortest paths between all pairs of nodes. The problem explicitly stated that you will only be given graphs in which there exists a path from every node to every other.

This is not a hard problem to work out, but anyone who has had a formal course in computer science ought to recognize that the Floyd-Warshall all-pairs shortest path algorithm is designed to solve exactly this problem. Then all you have to do is add up all of the elements of the matrix and divide by n * (n-1).

Except that the judges made a mistake, and tested our input using a graph that was not connected - in other words, there were nodes that could not reach other nodes via a directed path. This would not be a big deal, except that the problem explicitly stated that this would not occur. (Input validation is never a part of this contest.) Furthermore, without further explanation it is unclear how these nonexistent paths should affect the average. It turns out that the judges' solution was not counting these paths, and averaging only the paths that existed. Some teams did this by accident, and others (including Waterloo) figured it out only after submitting multiple runs and incurring large penalties. My team was one of the many that did not figure out the judges' mistake, so we did not get credit for the problem, even though our solution was certainly correct as the problem was worded. If we had received credit we would have had four problems correct, possibly putting us in the top ten. Of course, if we had received credit right away, we might not have wasted so much time figuring out what was wrong with our solution and we could have solved another problem in that time. Of course, many other teams were in a similar situation, so I have no idea what the final ranking would have been, but clearly it would have been different.

Now for some disclaimers.

First of all, I do not know firsthand that the judges had an incorrect data set, because their policy is not to release the data sets they use to test our programs. However, literally dozens of the 60 teams there encountered this error and many of them gained serious evidence that this was in fact the exact error. For example, one person showed me code he had written that would cause the program to seg fault if and only if the graph was not connected. He turned it in, and he got "runtime error" from the judges, indicating his program crashed. When he removed that line, he got "wrong answer". Even the team from Waterloo agreed that the data set was faulty.

Also, I am not trying to imply that the teams that did win did not deserve it. All of the top teams did an excellent job and deserve to be congratulated. I'm mostly upset that the ACM contest staff will not either admit there was an error, or release the datasets to prove there wasn't one.

Dominic