The Fumbling Bumbling ACM ECNA Regional

The test data for the regional was finally published. One test case for problem B violated the input spec. My team (CMU Tartans) solved that case "correctly" (whatever that means for an invalid input) while Waterloo Black and CMU Dragons solved it "incorrectly". Those runs will have to be rejudged and the scoreboard recalculated.

To preface this I will say that I am pissed because there is a good chance that after being a regional winner for 5 days there is a good chance we won't go to world finals. Right now it looks like Waterloo got 1st, CMU Dragons got 2nd, CMU Tartans got 3rd, and Michigan got 4th.

The first big mistake was not checking the test data. I helped create the problem set for the CMU Invitational. For all of the problems I wrote I made my solution check the input format and verify that all of the test cases were valid. It is a simple sanity check to make sure the problem specification matches the test cases.

The second big mistake was not checking the test data right after the contest. The problem decided world finals spots its probably worth checking. If they had asked either of the two top teams that missed the problem with many resubmits they would have been told that there is a decent chance of a bug in the test data. If they had looked at the one test case which everyone was failing they probably would have seen the bug. Instead they just glanced over things and missed it completely. They should also have realized that they screwed up test data the last two years, which means there is a decent probability they did it again.

It is hard to write a completely correct problem set, but it isn't that hard. More importantly the contestants deserve a better contest. We practice countless hours to do well in this one contest, and they can't put in the time to make sure that their problems are correct?

There was another, smaller, error in the problem set. On problem H the number of queries is not limited. Thus there is a valid input file of infinite size. When we first read it we thought that you might need some fancy data structure because their could be a huge number of queries. It turns out that nothing special is needed. The problem is that for every solution judged correct there is a huge input file that makes it time out. That didn't cost us the problem, but it definitely cost us time penalty.

ACM ECNA Regional 2009 Part 2

We found out some more information about the 8 minute error from the regional. All sites but Youngstown started on time. The contest was essentially 5 hour and 8 minutes long, and Youngstown started 8 minutes late. The solution itself is not great. I would have preferred running 5 hours for all sites. Youngstown would have an advantage because they would be able to look at the scoreboard 8 minutes in the future from other sites, but it is a very small advantage.

But what I really don't like about the solution was that the judges were okay with it because no top teams were from Youngstown. I think that one of the key parts of a competition like this is that it doesn't matter where you start from, as long as you show up to the competition you are on even ground. Sure its nice to get preferential treatment but fundamentally it isn't fair. I realize that when there is some sort of mistake there isn't always a fair way to fix it, but I don't think top teams should be given any thing extra just because of paster performance.

At this point we aren't sure whether or not there is a problem with B, because the test data has not been published. At this point I'm willing to give the judges the benefit of the doubt, but I'll post more about it once we figure out exactly what happened on the problem.

ACM ECNA Regional 2009

The final standings are here. As usual the contest report doesn't mention any technical problems. I thought I would mention the ones I heard of here.

When the contest started the McMaster site had not yet handed out problems. So after PC^2 was started it was stopped again, then the contest was started over 8 minutes later. At least at my site we started and were never told to stop, and didn't check PC^2. I believe that the other sites except for McMaster did the same thing. Essentially McMaster was 8 minutes late to a 5:08 long competition. Its not fair, but it shouldn't change the results of the world finals teams.

The time left on PC^2 was wrong for about the last hour of the contest. It showed < 2 minutes left for about the last hour. We were done at that point so we were unaffected. This is a huge problem for teams still working because it makes it much harder to manage time. The other CMU team was printing every few minutes because on the printout was the current time.

The last issue may or may not be an issue. At this point I'm willing to give the benefit of the doubt to the judges. Most of the teams who got B incorrect (Waterloo, CMU Dragons, Purdue) weren't sure why they got it wrong. There are rumblings that the test data was wrong, or that there was floating point error. I haven't throughly checked our 4 wrong answers to that problem, but at this point I believe all 4 of them were incorrect. After the floating point debacle of last year I think the judges probably checked the problem very throughly before finalizing the results.

When the test data is released for B we'll be able to go back and figure out why teams were getting wrong answers. The problem was hard to code, and hard to debug so it is plausible that teams just had subtle bugs in their code.

The final results were CMU Dragons in 4th, Waterloo in 3rd, University of Michigan 2nd, and my team, CMU Tartans in first. My team had plenty of good luck on our side. We weren't affected any of the issues and potentially we got B right despite rounding errors in the test data. Either way we are headed to Harbin China in February.