This week in competitive programming

2014 is coming to an end, but the algorithmic competitions are still in full swing. Codeforces Round 284 happened on Christmas Eve (problems, results, top 5 on the left). Top 5 is full of usual suspects, and this time Egor Suvorov is on top - congratulations!

TopCoder SRM 643 picked up the competitive spirit right after the Christmas holidays (problems, results, top 5 on the left). Both the easy and the medium problems required ad-hoc solutions that were easy to get wrong - I got trapped twice, resubmitting both problems - so the round was decided during the challenge phase. zerokugi and wleite achieved amazing +425 points from challenges each (9 successful + 1 unsuccessful), but zerokugi also got both problems correct and claimed the first place - awesome performance!

The easy problem asked you to factor a number up to 10¹⁸ into a product of primes, but with some extra help: you were already given every other factor in sorted order, starting from the smallest factor, then the 3rd smallest factor, and so on. The most probable mistake here was accidentally doing 10⁹ operations for a tricky testcase and thus running out of time.

The medium problem studied a table zeroes and ones with two rows and at most 200 columns. In one operation, you could either change a single element to be equal to one of its adjacent elements by row or column, or change an entire column to be equal to one of its adjacent columns, or change any horizontal contiguous segment in one of the rows to be equal to the corresponding segment of another row. In this problem there are a lot of different correct greedy and dynamic programming solutions, but even more different incorrect greedy and dynamic programming solutions.

I was aware that both problems were tricky before the challenge phase. Given that I knew only one way to fail the first problem, and a lot of ways to fail the second problem, I've decided that it would be much easier to look for the mistake in the first problem and tried to challenge those solutions. In hindsight, this was obviously a wrong decision, for the following reason: despite there being many possible mistakes in the second problem, every mistake means that we're handling some small pattern incorrectly. So if we take a random 2x200 table, it will most probably contain the corresponding bad pattern for every possible mistake, and we can just challenge all solutions blindly and very quickly without actually finding what each mistake is.

It seems that making good logical decisions for the challenge phase is still tough for some reason :) Thanks for reading, and check back in 2015!