Slashdot Mirror
ACM Programming Contest Results Revised
Goonie writes: "After the controversy over the results of the ACM programming competition, it appears that the results are being revised. Check out the new standings. The winner hasn't changed, but some teams have moved up the rankings." Actually, from the look of the page at 4:15GMT this morning, "final rankings are under review." Let's hope the fairest decisions prevail, and that all involved are gracious.
I don't see how anyone could have made enough sense of it for there to be a controversy.
Damn good programmers, them.
Got Rhinos?
Check out this link about the Controversy over Problem F, and look for Dominic_Mazzoni's post (+5 interesting). I'll quote from that article:
Take a look at problem F. (Here are the contest problems 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.
"It's overkill, of course. But you can never have too much overkill." - Anonymous Slashdot Coward
Heh. You're thinking of the longest path problem, which is NP-complete. Finding the shortest path between a pair of nodes is easy - use a simple breadth-first search for an unweighted graph, or Dijkstra's algortihm for a weighted one.
To find the shortest path between all pairs of nodes, you can use the Floyd-Warsha ll algorithm, which runs in O(n^3) time. It can be done faster, but in this particular case we were guaranteed n is no more than 100, so this was quite reasonable.
Does anyone know which teams used what languages?
//John|3:16
The team from MIT spoke only in 13th century latin. The team from Oklahoma State communicated solely in cattle brands.
The team from NYU in Ebonics. The team from Dakota State University spoke only in a very slow drawl.
The team from Georgia Tech kept referring to functions as crackers, and arrays as yankees. The team from UCLA constantly threw in random "likes" like, like this, like.
The team from University of Winnipeg felt it necessary to say aye after each sentence. The team from University of Southern Florida wouldn't shut up about Elian, and often develoved into a Spanglish.
The team from Brigham Young University kept referring to the moral crumbling of the ACM contest. The team from Texas Christian University always commented their code in the form:
I was one of the University of Melbourne team (thats Melbourne, Australia).
;), others struggled with it for the entire five hours, trying to find bugs in their correct code.
;), but in this case (having spoken to several of the teams) I think most of those teams just came up against problem F and got stuck.
If it hasn't already been explained, problem F went as follows: find the average shortest path length between all pairs of nodes in a strongly connected directed graph. The judges appear to have put a non-strongly connected graph in the testing - one for which not all pairs of nodes have a connecting path. It was then pure luck whether you had chanced upon the same method for computing the average as the judges, so while some teams solved the problem in the first few minutes of the contest (notably St. Petersburg state U.
Because it was by far the easiest of the problems, many teams began with this question. By the end of the five hours, many perfectly clever teams had not solved anything, due to the stuff-ups on the part of the judges.
Now, making errors is one thing, and it certainly screwed up the contest for everyone, but in some sense errors are forgivable - what was really appalling was the way in which the situation was handled.
A protest regarding the question was submitted (by my team) within a minute or so of the end of the contest - there was no official channel for appeals, so we were just told to write it down on a piece of paper and give it one of the judges. We never received a response of any sort.
After the contest most of the teams were aware of the problem - one team had submitted a program designed to go into an infinite loop if the input graph was not strongly connected, thus working out what error the judges had made. In any case, we took our printouts to verify our solution, and later presented our arguments to the tournament director, Bill Poucher.
I have never met someone so unprofessional, with no concept of accountability or responsibility, and little even of courtesy. I am not sure what his background is, but if Mr. Poucher were the director any public company, he would have been on the street - or in court - in seconds. He refused to listen to any of the requests from the teams or coaches, telling them instead their memories of the contest perhaps weren't clear. Nothing was done and the prizes were awarded, with Bill Poucher announcing at the ceremony that "every problem was solved by at least one team" - so that there weren't any problems.
After the contest, in the face of protests from regional directors and coaches from around the world, with proofs that their solutions had been correct, the contest organisers continued to deny there had been any problem. It took quite a while for them to agree to remark the solutions.
Now, I have no especial gripe at the judges that an error was made, because people make mistakes - it's just an indication that they need better validation on the testing programs. I'm also not especially fussed that my team didn't come first - because in some sense, we were one of the LEAST affected teams. Just look at the results of the American universities. I mean, it's nice to have a laugh at America getting its ass kicked once in a while
What I do have a problem with is the contempt the organisation showed to the tens of thousands of man-hours of work that go into the contest on the part of the contestants. No channel for appeals, no official responses to protests, no means to elect new directors, no accountability, not even a report saying "we made a mistake; we plan to do this to fix it". There was a similar problem in our regional contest this year, and the regional director (Raewyn Boersen) fessed up, and sent around an email describing the problems, the changes she would put in place to the validation of the competition, and the transparency with which future contests would be conducted.
My question for slashdot is, how do you get an organisation like this to to act like it's accountable to the people who enter?
In any case, I'd still recommend entering the contest to any CS students - its an amazing experience, however it goes. I've never learnt as much CS in such a short time as in the week's training leading up to the finals. Ask yourself - if you had to, how fast could you code up a 3D voronoi tesselation? Or a fast constraint solver? Can you find a bug in someone else's uncommented code under time pressure, or look at a problem and say how long it will take to code, and what the best order algoritm is? These are the kind of things you learn.
cheers all,
John FitzGerald, University of Melbourne,
Australia