ACM World Finals

Our plan going into the world finals was to slow down for the first hour so that we would tackle the correct problems in the problem set. We had not done that well at problem selection on the last couple of practices. The goal was to get 5 problems (the best CMU has ever done is 4), but I thought we were capable of 6 on a very good day.

We started out as we always do, Celestine (the fastest coder) reading A-C, I get D and every other after it (D,F,H,J) and Alan gets E and every other. Celestine recognized that A was pretty trivial very early on. He talked it over with me and we came up with the algorithm which he coded and got correct on the first submission. Already we had started out better than at regionals.

From there we didn't have an immediate next problem. I started working on F, and eventually got a rather crude algorithm for it. I talked it over with Celestine and he started to code it. After a few minutes he noticed a cool property that allowed the code to be significantly simpler (basically taking all the computational geometry except convex hull out of the problem). While he coded that up I talked over B with Alan, and started coding it out on paper.

Celestine got F correct, so I hopped on the terminal to type up B. Alan was working on E on paper while Celestine scavenged for another problem. My first two attempts at B were incorrect, but after some help debugging from Celestine we found the bugs (not implementation problems but a small misunderstanding of the problem). We finally got B done and Celestine went to code up I. I talked over E with Alan and we got an algorithm working that we thought was correct.

Celestine turned in I and got it wrong the first time. We found a small typo resubmitted and got it wrong again. We fixed another few bugs over the next hour or so, but we still didn't have it correct. Alan started typing up E while we finished up I. Celestine was still debugging I, when Alan turned it in and got it back wrong. I looked over it with him, and after a few minutes we were both confident in the implementation. It took a few more minutes before I found the counterexample. We quickly found a fix that would still reuse most of the old code. In the meantime I told Celestine to go from int to double math and to do another stupid fix just in the off chance one of those is our bug. We ended up having integer overflow so that fixed I. Alan quickly fixed E and we were finished with 5 before the scoreboard was frozen.

From there we went looking for more problems. Alan recognized that H is basically the 2-sat algorithm. He coded that while I watched, in the meantime Celestine looked at the other problems trying to find the next easiest one. Alan quickly finished H (whenever we pair program the debug time seems to be nearly instant) and got it right. We were a little worried about some parts of the algorithm, but I think that if I had more of a grasp as to why 2-sat works, not just the algorithm it would be easy to show that ours is correct.

At that point we had 6 problems left with about 35 minutes on the clock. We selected D as the next easiest problem, but despite our best attempts we didn't get too far on it. I think at the end we had some good ideas on how to solve it, but we were probably 30 minutes to an hour away from getting it.

With the contest over we milled about waiting for the results. It was really nerve wracking for us, we were in roughly 16th place when the scoreboard froze without a very good time penalty. We knew we had a shot at a medal, but it didn't seem like a good shot at the time. Eventually the scoreboard went final and our tiebreaker was good enough to put us ahead of most of the teams with 6 problems solved and in 12th place for a bronze medal.