Tuesday, May 9, 2006

TopCoder Open 2006

Just got back from the TopCoder Open 2006 finals in Las Vegas. For those unfamiliar with TopCoder events, they are computer programming competitions where contestants have to solve several programming problems in a fixed amount of time, usually around an hour. The problems can be quite difficult; I was eliminated in earlier rounds of the TCO 2006 after missing this problem:

You are given a NxN matrix M, where 1 <= N <= 50, and an integer k, where 1 <= k <= N. Write a function to determine the maximum possible trace value for a kxk submatrix S, created by taking any k rows and k columns from M. (The trace is the sum of the elements on S's main diagonal; the selected rows and columns are not necessarily contiguous.)

Anyway, the final rounds were quite dramatic, with the problems being tougher than ever, the elimination of some of the top seeds, and some close finishes in the rounds to select the competitors for the championship round. In the championship round, it came down to 8 competitors - mostly from Eastern Europe, with 1 each from China, Japan, and Australia.

"tomek" (from Poland) got out to an early lead by solving the 250-point problem (You are given two rectangular solids of arbitrary sizes; write a function to determine the minimal surface area of a box than can enclose them) in just over 5 minutes. However, "Petr" (from Russia) prevailed in the end by being the only competitor to solve the 1000-point problem (Given an array of cables connecting N points, where each cable has a quality Q and a cost C, select a subset of the cables such that all points are connected and the sum of the quality values over the sum of the cost values is maximal). Petr walked away with $20,000 for his efforts; he was also asked at the post-event press conference "What was the most important decision that you made during the competition that allowed you to win?" His answer, naturally, was "The most important decision that I made was choosing to solve the 1000-point problem correctly."

Below are some pictures I took during the competition. At first, it can seem a bit strange to think of programming as a spectator sport. TopCoder does an excellent job though, with multiple screens displaying the standings in real time and mirrored viewsof all the competitors screens so you can see how they are approaching the problems. When the competitors are this good, it is quite exciting to just watch them work.

No comments: