Monday, March 30, 2009

UVA World Finals Warmup I

It was the best of times, it was the worst of times.
Curt and I came into the practice with lowered expectations because John was out of town. In sports when a star player is out, the team often learns to adjust and as a result is better for the experience.
The competition started decently well -- we completed our first problem (B) in 30 minutes. Upon first glance, the problem appeared fairly complicated. But after the first read-through, I read through it again, to make sure I didn't miss anything. Then, so as to not waste any more time, I just coded it up. AC (All Correct)!
When that was finished, Curt had found another problem which looked fairly doable (D). We discussed for a couple minutes, and I coded that one up while Curt was figuring out how to do E. This problem was slightly more complicated, but not bad at all. The trick was to use a tree-like data structure, and solve it from the bottom up. I decided to create a new class with a linked list of children. Matching, the output, submit. RE (Runtime Error). Rats. I spent much of the rest of the competition trying to figure out what was wrong with my code. From what I could determine, it boiled down to incorrectly parsing some input. But after re-reading the question statement many times, and trying many possibilities, I couldn't find it. That problem never was solved -- in about 15 failed attempts.
The next problem I attempted was one on solving a game (A). DP allowed me to solve it in linear time, and from there it is just a matter of trying multiple combinations. Matching the output, submit. TLE (time limit exceeded). This is possibly my least favorite response, especially with the tight constraints of the UVA online judge. After making some optimizations (and finding a bug), I submitted it again. Remember, all this time I am tweaking problem D and re-submitting it. Problem A never got past TLE.
Curt, meanwhile was keeping himself busy. He had found a couple quite similar problems, and was working on one of them. He had it all coded and was matching the input. Unfortunately, he ran into a memory constraint with a fairly large array and didn't have time to re-code it.
At the end of the day (which was actually more mid-day), we had 1 success and 4 matching-but-unsuccessful problems.
Hopefully we will do better in the World Finals. Having John around will very much appreciated.

1 comment:

  1. I am so HUGELY IMPRESSED, by your achievement, by 'The Competition, by the crazy-brilliant 'brain-machines' God has given each of you - and that you have been brought to the same place at the same time for this great challenge! I am rooting for you to have calm and clarity, and that your brains click along at top speed! Congratulations on the honor of being in the TOP 100 WORLD COMPETITOR TEAMS!
    ~Victoria Karssen, OC, NWC alum

    ReplyDelete