ACM ECNA Regional 2008

I never wrote a blog post about how the regionals went down, so here goes. We came in as the B team from CMU. We had only practiced a couple times with the A team and they beat us both times, once by a narrow margin and the other by a big margin. I thought we were getting more practices in, but either way we were the underdogs.

I started the contest off really nervous. I started by reading problem C which was a pretty trivial problem. I was scared about accidentally jumping on too hard of a problem at the start, but after I few minutes I went for the terminal. The problem was pretty simple and I submitted it, only to get it back with a wrong answer. In the mean time Celestine who was assigned problems A and B started working on B, probably not what he should have started working on but it was a doable problem. Alan started on D and also got back wrong answer. 45 minutes in we had two wrong answers already, and no correct submissions.

Alan and I helped each other out debugging code while Celestine started on B. Eventually I fixed my bug and got our first correct answer 50 minutes in, and Alan followed with his problem 6 minutes later. Alan went for E, while I helped Celestine with B and started looking at the last few problems. Alan finished E pretty quickly while Celestine was having problems with B. I worked with Celestine to get B wrapped up and get the significant figures worked out. We turned in B and somewhat surprisingly got it right the first time.

I'm not sure when, but I think about now we decided that we weren't going to get all 8 problems, so we canned A and just went for seven. I wrote up my somewhat hacked together program for F, it worked first time but I really didn't think that it was going to. After we got it right we checked the scoreboard and saw that we were in the lead (which I think is a bug because looking at the submission times we were never actually leading). Celestine identified G has brute force (despite by disbelief) and he went to work on that. In the mean time I worked on H with Alan. We started with a pretty simple solution, but we found some counter examples and had to make it more and more convoluted. Thankfully the bounds on the problem were so small that an extra factor of n in the runtime didn't hurt.

Celestine submitted G and got it wrong. While he was debugging Alan went to type of H, and I helped Celestine debug. We found Celestine's bug which I think was something small like swapping his is and js in some nested for loops. We had fifteen minutes left to finish off H. The scoreboard was locked with an hour to go and the top 3 was us, the other CMU team, and Waterloo, all with 5 problems solved. Our tiebreaker was pretty horrendous with 4 wrong submissions and a really slow start. At that point I thought we had no chance of winning the contest.

Alan debugged his code while I watched him and Celestine worked on some test cases. The clock was slowly ticking down and we couldn't even pass the example test cases. With one minute left on PC^2 (which means less than 2 minutes actually) we finally passed the example test cases and turned in the code. We didn't bother typing up the example test cases until after. We put them in and everything seemed to work. The contest ended and we still hadn't gotten a response back. At this point Alan was shaking uncontrollably. I thought that even with the seventh problem we would be in second or third because of our tiebreaker.

Eventually we got our submission to H back correct. The other CMU team came in and asked us how many we solved (the scoreboard was still frozen) we had seven, they had six. At that point whether we won the regional or not we were going to the world finals. I was still pretty sure we hadn't won overall. When we got to the coaches area the scoreboard was up and CMU had gotten first and second. We were the only team to solve seven.

I have been wondering how lucky we got to win the contest. After the fact Waterloo challenged the fact that their submissions to B were wrong claiming that it was a round error. They used ieee rounding instead of the normal rounding. The problem should be setup so that doesn't matter. The other CMU team said their submission to H would have worked if they had gotten the tiebreaker right for which path to pick. Our submission to H could have easily gone the other way, but it all seemed to work out in our favor.

In the end there was a big chunk of luck that helped us, but I think out team strategy was more of the deciding factor. The decision to not even attempt A was pretty crucial to us. We didn't waste any man power on it, while the CMU team (and maybe the Waterloo team) spend some time trying to figure it out. I think out use of console time was done really well, we didn't do much debugging on the console, lots of team debugging on paper.

On the other side our problem selection was pretty horrendous. We got E (one of the 2 easiest problems) two hours into the contest. We started B as one of our first problems (which only two teams ended up getting). In the end though if you solve seven problems and no one else does it really doesn't matter how you solve those seven problems. This is also an example of how for a team solving most of the problems at a regional problem selection can't hurt you that much. Sure our time penalty got hit pretty bad, but it didn't make us solve fewer problems. If a team who was only going to solve 4 problems went after B as their first problem they will probably only end up solving 2 or 3 problems.

With that win we are off to Stockholm in a week. After a winter of practicing I think it is going to give us a trip to the next world finals. The previous CMU A team hasn't been practicing much at all. For them to compete with us at next year's regionals they are going to need to put in a ton of work. Thinking back if the regionals go the other way and we don't put in the practice over the winter we could have effectively lost this year's regionals, and next year's.