This week in competitive programming

TopCoder SRM 633 took place on Wednesday (problems, results, top 5 on the left). The hard problem was nice, but the medium problem was even nicer — kudos to the problemsetter, cgy4ever! You were given two trees with the same set of vertices, each vertex had a (possibly negative) score assigned to it, and you needed to find a subset of vertices that is connected according to both trees and has the highest total score. The question is very simply stated, and yet the solution is quite challenging and creative — that's how great programming contest problems look like! Can you see it?

A flawless peformance by Gennady guaranteed him a clear first place. Great job!

Codeforces Round 268 happened on Saturday (problems, results, top 5 on the left). I've skipped this round but I can still see that Pavel achieved a commanding victory thanks to 10 challenges in a contest where many top scores couldn't find any — amazing!

We've also had some very nice developments in http://hamiltonianplumber.appspot.com/ during the week: +Boris Minaev found a creative way to break the 2-opt heuristic with random restarts. To quote him:

"my idea is very simple - creating a big test is hard, so we can create a small test (for example with 10 vertices) and then repeat it 5 times. By repeating I mean placing vertices of different groups far from each other. In such test case the correct order will be (visit all vertices of 1st group) -> (visit all vertices of 2nd group) -> ... (visit all vertices of 5th group). If we now look at number of iterations that 2-opt solution need to find a correct answer, it would be something like (number of iterations it needs to find a solution for one group)^5.

So we just need to create a small test where 2-opt solution works bad. This we can do with just a stress-tesing. It's easy to find a test which needs ~10 iterations of 2-opt, which gives ~10^5 iterations in total."

This testcase forces the heuristic to make 230932 attempts before finding the shortest path for the first time:

{690, 9932, 10000690, 10009932, 20000690, 20009932, 30000690, 30009932, 40000696, 40009883}

{1175, 1327, 1564, 2263, 2715, 7246, 7674, 7997, 8334, 8511, 10001175, 10001327, 10001564, 10002263, 10002715, 10007246, 10007674, 10007997, 10008334, 10008511, 20001175, 20001327, 20001564, 20002263, 20002715, 20007246, 20007674, 20007997, 20008334, 20008511, 30001175, 30001327, 30001564, 30002263, 30002715, 30007246, 30007674, 30007997, 30008334, 30008511, 40001663, 40003713, 40003852, 40007375, 40008436, 40009682, 40009842}

// please don't upload it to the server just for the sake of getting to the scoreboard — it actually requires quite a lot of resources to judge!

If you want to test your hamiltonian path implementation, you can construct the actual graph using the first part of the code in http://hamiltonianplumber.appspot.com/source.html.

And finally, it's time for some celebration as this is the 52nd post titled "This week in competitive programming" (here's the first one), meaning that this weekly programming contest review has been going for an entire year! I guess the expected question is: what do you think I should improve in this blog?

Hoping for sincere feedback, and see you next week in any case!

Tweet