This week in competitive programming

TopCoder SRM 617 took place on Monday (problems, results, top 5 on the left, my screencast). Instead of sharing a problem to solve, I want to share a challenge opportunity that I found in this match. It was in the medium problem, which can be described as: you are given an undirected graph, and want to assign a direction to each edge such that sum of absolute values of in-degree minus out-degree for each vertex is as small as possible. The solution I challenged went like this: let's assign a random direction to each edge, and then repeatedly reverse an arbitrary edge that would reduce the cost function. Then, we repeat the whole process 500 times and pick the best result. Can you come up with a challenge case (the graph has at most 50 vertices and at most 1000 edges)?

TopCoder SRM 618 took place on Friday (problems, results, top 5 on the left), at 5am Moscow time. This was too much, and I've skipped this one.

Google Code Jam Round 1A took place on Saturday (problems, results, top 5 on the left). I was the author of the third problem, which I like a lot, and encourage you to try solving it if you haven't already - the Code Jam website allows you to submit your solutions even if you hadn't participated in the actual contest. The problem basically gave a buggy (but reasonably good) algorithm to randomly shuffle an array, and you had to determine whether the buggy or the correct algorithm was used just by looking at the generated array.

TopCoder Open 2014 Round 1C took place later on Saturday (problems, results, top 5 on the left), with the field getting a bit weaker with most top competitors having already qualified for Round 2, and the problems were made correspondingly easier - so easy, in fact, that the coder with handle 'Min,lu' has taken the third place in the TopCoder record book by solving three problems correctly and spending just 10 minutes in total!

Those who already qualified could take part in Parallel Round 1C which used the same problems (top 5 on the left). The winner 'fetetriste' solved all three problems while spending less than 9 minutes, so he would've also get a high spot on the above record table - but the parallel round was unofficial and its results won't appear in the stats database.

And finally, Codeforces Round 243 happened on Sunday (problems, results, top 5 on the left, my screencast). The round had some nice problems, out of which the following was the nicest - if a bit well-known - one: you are given 100000 points on the plane. How many squares are there with sides parallel to the coordinate axes and all four vertices in the given points?

Thanks for reading, and see you next week!

Tweet