Sunday, January 5, 2014

This week in competitive programming

Happy New Year!

Last week was mostly holidays, but it still featured a programming competition. Codeforces ran its last round of 2013 on Monday (problems, results, my screencast, top 5 on the left). The problems were not bad but not too exciting in my opinion, but in the aftermath of the round a nice formula for creating nasty problems was born :)

Some more exciting problems are still open to be solved at New Year's Prime Contest (see my last year's description for details). Here's this year's link (Russian), PDF with problems, and the current standings. Problem 5 is still not solved by anybody, although its problem statement is not very clear, which might explain why nobody tries to solve it. I've particularly enjoyed problem 2, which goes as follows: you are given a 2000x2000 matrix of zeroes and ones, and need to find the number of permutations of its columns that result in a matrix where ones in each row are consecutive (see the PDF for details). Squeezing it into the time limit might not be too exciting, but coming up with any polynomial solution certainly is. I'm also the author of problem 31.

And finally, I want to share a picture of a New Year's gift from my dear wife Irina: it's a bed cover made from old T-shirts, mostly from programming contests. This might be a bit too personal for this blog, but I hope it's enough of a programming contest artifact :)

Thanks for reading, and see you next week!