TCCC05 in Review, by Steven Skiena, PhD
As a programming contest maven (which is Yiddish for "self-proclaimed
expert"), I found attending the finals of the TopCoder Collegiate Challenge
a very interesting experience.
I was extremely impressed with the caliber of the students who made
the finals. Obviously they were all great hackers, but they were also a
much more interesting, accomplished, and well-rounded gang than I could
have expected. In particular, I was amazed that the winner of the
algorithms competition, Mathijs Vogelzang, was a medical student.
Several of the other finalists were math and physics students, and most
of the students I talked to were pursuing advanced degrees. I particularly
recall interesting discussions on the Australian economy with John Dethridge
and the state-of-the-art in natural language processing with David Vickrey,
I have been asked to comment on the three problems appearing in
the final round. The Level One problem concerned counting how many
strings could be formed on a three-letter alphabet avoiding two forbidden
strings S1 and S2 as substrings. The input lengths are clearly too large
to permit a construct-and-test solution. Instead, one must use dynamic
programming, where the state reflects the number of strings of a given
length ending in the last i characters of S1 and last j characters of S2.
That both mathijs and tomek could get this working correctly with so much
time pressure is an impressive feat.
The Level Two problem concerned finding the comparison plan for
minimum cost sorting of files under an unusual cost function. Readers of
Knuth, volume 3 on optimum sorting (pages 181-195) will recall that finding
such optimal comparison plans require enumerating through partial orders.
The number of partial orders on up to six elements is a large number, and
hence the key to this problem is doing this efficiently enough. Attempting
this problem requires considerable courage (I called it something different
during my talk..) because it is hard to be certain that it will complete
in time. This was a very tough problem.
The Level Three problem asked for the optimal evaluation strategy
to bound the maximal value of a unimodal function. This problem was a little
dirty, in that there was a very simple solution based on Fibonacci numbers
if you saw it. Indeed, if you go to Knuth, volume 3 on Fibonacci search
(pages 414-416) it describes a Fibonaccian search procedure that can be
used for this problem.
That two of these problems have solutions at least inspired by good
old Knuth should be a lesson to TopCoder contestants -- spend some time with
his wonderful old books. You can ignore the assembly language, but enjoy
the problems and ideas which always seems to pop up in amazing places.
Steven Skiena
Dept. of Computer Science
SUNY Stony Brook