This week in competitive programming

In contrast to last week, this week was quite light on programming contests. Late on Saturday, the final online round of the Facebook Hacker Cup took place (my screencast, top 5 on the left). Several things went wrong at the same time for me. First, I've spent an hour on the easiest problem by making a somewhat classical mistake: the problem statement had a constraint n_i<=4, and I immediately started thinking about solutions that rely on that constraint. It turned out that the correct solution works fine even for large values of n, and is much, much simpler that what I came up with during that hour. Then, I've implemented the solution for the third problem with the correct big-O asymptotic complexity, but without caring too much about the constant factor, and couldn't reduce the constant factor under the pressure of the last 30 minutes of the contest. I've made a desperate attempt to still run my solution against judges' input, but it timed out as expected.

When two problems go wrong at the same time, getting into the top 25 in the world is too hard, so congratulations and good luck to everybody who made it to the onsite finals!

On Sunday, TopCoder SRM 601 took place (problems, results, my screencast, top 5 on the left). Both the medium and the hard problems required tricky dynamic programming: the solution that comes to mind right after reading the problem has too many states in dynamic programming, so you have to somehow reduce the state space. While both problems look a bit artificial and thus not as exciting to solve, they are a good way to practice advanced dynamic programming if you want to (medium, hard).

Thanks for reading, and see you next week!