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!

This week in competitive programming

On Wednesday, Codeforces ran a normal round with an unusual title: Russian Code Cup 2014 Warmup (problems, results, top 5 on the left) with problems from the organizers of Russian Code Cup 2014, which we'll talk about below. I didn't take part, so I can only share a funny Swistakk's quote with you: "tourist had so much luck in this contest :P! Egor on 2nd place got TLE on E, because TL was very tight and flashmt on also 2nd place got TLE on A, because of endl's instead of \n and they will easily win if it weren't for those unlucky TLEs!" As the saying goes, fortune favours the bold!

Early on Saturday, the first qualification round of the Russian Code Cup 2014 took place (problems, results, top 5 on the left, my screencast). Russian Code Cup is a big competition with problems in Russian ran by Mail.Ru and ITMO. The round had quite a lot of technical issues, which was a pity since the problems themselves were nice.

Later on Saturday, Round 1B of the TopCoder Open took place (problems, results, top 5 on the left). The round saw many veterans at the top of the standings: krijgertje participated for the first time since TCO12, SnapDragon, meret and peter50216 participated for the first time since TCO13 - and they're all in top 7!

At the same time, people who have already qualified could try the same problems in Parallel Round 1B (top 5 on the left, my screencast). The problems had easy-to-understand statements but required some creativity to solve. Here's the medium difficulty one: you are given a 16x16 grid where some cells contain wolves, some cells contain sheep, and some are empty. You are allowed to build infinitely long vertical and horizontal walls along grid boundaries. What is the smallest number of walls needed to separate the sheep from the wolves?

Finally, on Sunday, the last round of this year's Open Cup took place (results, top 5 on the left). It had fewer participating teams than usual, but at the same time the teams from China showed impressive results, reminding that we shouldn't forget about them when making predictions for the ACM ICPC World Finals.

Here are the overall Open Cup standings. The top has a nice mix of veteran teams, like my team or the XZ team, current ACM ICPC competitors like SPb SU 4 and Moscow SU Tapirs, and the winning team tourist in a class of himself :)

Thanks for reading, and see you next week!

This week in competitive programming

This week was so busy that I didn't have time to solve programming contests, so here's just a quick summary of their results.

TopCoder SRM 616 took place on Thursday (problems, results, top 5 on the left).

The first round of TopCoder Open 2014, Round 1A, took place on Saturday (problems, results, top 5 on the left).

However, top 250 by rating who have participated in SRMs in 2014 were automatically advanced to Round 2, and there was a special Parallel Round where those could compete (same problems as Round 1A, top 5 on the left). Surprisingly, the top fives of both rounds are comparable.

Google Code Jam 2014 Qualification Round ran for 27 hours between Friday and Saturday (problems, results, top 5 on the left).

And finally, the 13th round of the Open Cup took place on Sunday (results, top 5 on the left).

Thanks for reading, and check back next week for a hopefully more informative report!

Google Code Jam 2014 - just 10 hours left in the Qualification Round!

The qualification round for Google Code Jam 2014 has started, and will run for about 10 more hours (until 6am on Sunday Moscow time). If you haven't already, you should take part. I'm involved with preparing problems for this competition like last year, and hope you will like them :)

Note that the time when you submit your solution doesn't matter in the qualification round, so those who started before you have no unfair advantage. You just have to submit before the round ends.

Also note that you must not discuss the problems and solutions with others before the round ends. Online programming competitions are based in a large part on the honesty of their participants, so don't spoil it for everyone!

This week in competitive programming

TopCoder SRM 615 took place on Friday (problems, results, my screencast, top 5 on the left). The medium problem asked a somewhat classical but still interesting question: given an undirected graph with at most 50 vertices, at most 50 edges, and relatively small integer edge lengths (up to 10000), is there a path from vertex 1 to vertex 2 that is exactly T long (where T can be very big, up to 10¹⁸)? The path can of course pass through the same vertex or edge many times.

This question turned out to be really tough - it was only solved correctly by 17 contestants, compared to more than 100 contestants solving the hard problem which was supposed to be more difficult. I guess the point value for this problem was set so low because it's standard, so the judges assumed people would know how to solve it?..

Open Cup has returned on Sunday with its 12th stage (results, top 5 on the left). This round had wider participation than usual with strong teams from the United States and China in the standings. 39 teams that will participate in the ACM ICPC World Finals in June were participating, and here's the link to standings filtered to only those teams.

And finally, Codeforces wrapped up the weekend with their Round 240 (problems, results, top 5 on the left). I didn't solve the round myself, so I don't have anything to say about the problems. The round's winner was decided on challenges, which are always a big gamble in the Codeforces format where you have to choose between spending time on challenges early in the contest (while the points for each unsolved problem are ticking down) and solving the problems first (while the easy challenges are taken away by others). Personally, I think that challenging early makes sense only if you're looking for a concrete mistake that you can spot in several seconds, so that you can gain a lot if the mistake turns out to be widespread, or give up quickly if people don't seem to make that mistake.

Thanks for reading, and see you next week!