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.

Saturday, March 28, 2009

Introduction & Schedule

John Calsbeek, Curt Van Wyk, and myself (Ben Kester) qualified for the World Finals ACM competition.
Since this quite an honor, writing a blog seems fitting. There are a few reasons why I am creating this blog:
- To aid in remembering this experience down the road
- To give family and friends updates on the preparation
- To provide a resource for other teams in preparation
- To notify everyone back home on events of the actual trip.

This will be a rather odd collection of tidbits from our preparations. Many of the posts will probably be rather technical, though not necessarily all them.

Our schedule will be something like the following:
3/28/2009 -- This blog was created!
3/29/2009 -- UVA online competition, "World Finals Warmup I" (9 AM CDT)
4/5/2009 -- UVA online competition, "World Finals Warmup II" (3 AM CDT)
4/18/2009 -- Arrive in Sweden
4/21/2009 -- Competition from 9:30 - 3:00 (2:30 - 8:00 AM CDT)!
4/22/2009 -- Return to the States

Resources:
http://cm2prod.baylor.edu/ICPCWiki/Wiki.jsp?page=World%20Final%20Schedule%20of%20Events -- Schedule of events for the world competition
http://icpcres.ecs.baylor.edu/onlinejudge/ -- UVA online judge (lets you practice problems online, offers competitions)
http://acm.uva.es/board/ -- forum for UVA online judge (a great reasource if you get stuck on a problem)
http://www.catonmat.net/tag/algorithms -- MIT algorithms class lecture videos and notes
Programming Challenges: The Programming Contest Training Manual by Steven R. Skiena and Miguel A. Revilla