Monday, October 20, 2014

This week in competitive programming

Let's start with a poll: what would be a good name for this blog? Vote in my Google+, and suggest other options in comments! Now, back to business:

TopCoder SRM 636 on Tuesday had quite diverse problemset (problems, results, top 5 on the left). The easy was a pretty straightforward implementation involving several nested loops and a standard way to find sums of sub-rectangles of a given grid in O(1) after precomputation. The medium was a very unexpected application of linearity of expectation — such problems never cease to amaze me! The hard was a "professional" problem requiring both an insight and quite careful implementation to get right, which I haven't managed this time.

Even if my solution for the hard didn't fail with both timeout and wrong answer, I would only get second place. The first place is undisputedly Endagorion's — great job Mikhail!

The new season of the Open Cup started on Sunday with the Grand Prix of Saint Petersburg (results, top 5 on the left). I don't think the problemset is available online yet, but one of the problems was a very simply stated mathematical puzzle that I can share here:

Given an undirected graph where the degree of each vertex is at most 5, prove that it's possible to color its vertices using 3 colors in such way that each vertex has at most one adjacent vertex of the same color as itself.

Another problem has introduced a new concept that I don't remember seeing in programming contests before: you were asked to implement a strategy for a game, but instead of beating the optimal play of the opponent, your strategy had to beat random play of the opponent in at least 290 out of 300 rounds. Are you aware of similar programming contest problems?

Overall, this was a nice contest — kudos to the problemsetters!

Codeforces Round 274 (problems, results, top 5 on the left) happened right in the middle of the Open Cup round, so everybody had to pick only one of the two. As evident from the scoreboard, there was still quite fierce competition and Bruce ended up on top with 200+ point margin — congratulations!

Bayan Elimination Round wrapped up the highly competitive Sunday (results, top 5 on the left). I don't think the problems are available online, and I did not participate myself, but quite a few strong algorithmists did. Kazuhiro, one of the problemsetters of TopCoder SRM 636 mentioned above, has topped the scoreboard with a substantial margin — well done! This contest was notable for its highly unusual advancement system: only the top one coder from each of top 20 countries would advance to the onsite finals, essentially splitting the competition into many intra-country micromatches. Now quite a lot of people got to feel like many Moscow State University teams feel each year at the ACM ICPC regionals :)

Thanks for reading, and check back next week!

Monday, October 13, 2014

This week in competitive programming

Codeforces Round 272 was the only regular contest during the last week (problems, results, top 5 on the left). The problemset consisted of two relatively simple mathematical problems A and B solved with formulas that can be figured out using pen and paper, two dynamic programming problems C and D that had a few tricky implementation details to take care of, and an extremely tedious O(nlogn) data structure problem E that did not require anything more complicated than a stack and binary search, but needed more than an hour to implement and had a lot of possible plus/minus one errors to make.

There was another online contest held on Saturday, Marathon24, which is very similar in format to Challenge24: mostly solving optimization problems instead of pure algorithmic ones, the online part takes 5 hours but people who advance will participate in a 24-hour onsite competition. I didn't participate, but some quite strong teams did; I'm not sure if the final results are available online since the standings mention that they are still frozen. Maybe somebody reading this blog can confirm if the final results are already available?

Thanks for reading, and check back next week!

Monday, October 6, 2014

This week in competitive programming

The final round of Russian Code Cup 2014 took place on Saturday (problems in Russianresults, top 5 on the left), but it went without the official onsite event like we had last year, as the organizers decided to cancel the onsite part and hold the final round online. The monetary prizes were still up for grabs, and Gennady has claimed the biggest one with just 2 minutes to go!

Problem C was the highlight of the competition for me. You were given a positive integer M, and were asked to come up with an instance of the knapsack problem which has exactly M solutions (well, to be precise, M had to divide the number of solutions, but all approaches I know yield exactly M). More precisely, M was up to 1018, and you had to find at most 200 positive integers ai, each up to 500, and another positive integer W up to 500, so that exactly M subsets of {ai} sum to W. Some ai might be equal, but they are still treated as different for the purpose of subsetting. I encourage you to try solving this problem, you can submit your solutions at the Codeforces gym!

TopCoder SRM 635 took place later in the evening (problems, results, top 5 on the left). This round had problem statements in English unlike the Russian Code Cup, but the top 3 were exactly the same, Gennady claiming the first place thanks to the ultra-fast solution for the hardest problem.

That problem went like this; how many sequences of integers between 1 and 4 exist such that adjacent numbers are different, and there are exactly n1 ones, n2 twos, n3 threes and n4 fours? n1 and nare up to 200, n3 and nare up to 50000. Similar problems appear in competitions time and time again, but every time they turn out surprisingly difficult to implement. Can you see an approach that leads to a simple implementation?

Bayan 2015 Contest Warm Up happened on Codeforces on Sunday (problems, results, top 5 on the left). Conratulations fotile96, hogloid and sankear on solving all problems!

Thanks for reading, and see you next week!

Monday, September 29, 2014

This week in competitive programming

Another quite typical week drifted past, with a TopCoder round and a Codeforces round. First, TopCoder SRM 634 took place very early on Friday morning (problems, results, top 5 on the left). The early start was too much for me, but I want to congratulate mikhailOK and piob on solving all three problems and thus leaving the rest of the competition far behind — great job!

Codeforces Round 270 occupied the Sunday evening (problems, results, top 5 on the left). The problemset had a very nice common background story: each problem explained how one can come up with problems of this type — consider reading them all if you look for inspiration for creating new problems.

The hardest problem brought an interesting aspect of the programming competitions into the limelight: sometimes the expected algorithms get so complicated that the constant hidden in the O-notation of their running time is so big that solutions that are very straightforward and efficiently implemented can be faster even despite worse asymptotic complexity. In this particular problem, the reference solution from the editorial has complexity O((nlogn)1.5), while most, if not all, accepted solutions have complexity O(n2). With n as high as 200000, one might think that the extra square root of n will dominate, but since the n squared solutions are very straightforward and thus can easily be optimized, for example using bitwise operations, this is not the case.

ilyakor's accepted solution is the fastest, solving the worst testcase in just 2.5 out of 7 seconds by reusing a publicly available SSE3-based code for counting the number of elements in a bitset — a great use of all available resources to solve the problem! But as far as programming competitions in general are concerned, we've mostly given up on separating O(n2*polylog(n)) algorithms from O(n3) ones, and it's sometimes even difficult to separate O(n*polylog(n)) algorithms from O(n2) ones. It's a pity since we eliminate a large class of quite beautiful algorithms and data structures this way :( Any ideas on reversing the trend?

Thanks for reading, and check back next week!

Monday, September 22, 2014

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 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

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!

Tuesday, September 16, 2014

More on the Hamiltonian Plumber

This Sunday, I've launched a website with the goal of learning about good testcases that break a heuristic solution for a decisive TopCoder Open problem that can be reduced to Traveling Salesman:

So far, nobody except myself has submitted a testcase that makes the solution do at least two iterations — in other words, greedy improvement works in all submitted testcases. This is quite disappointing, so I'm wondering what's the reason for that. It could be:
  1. The challenge is not interesting enough, so people either don't bother at all or try a few manual tests.
  2. The website is confusing, so people don't understand what's really going on.
  3. The website is broken, so people submit good testcases but they are scored incorrectly.
  4. Something else? Please share what you don't like about the challenge!
Let me also share a simple strategy that allows to get a score higher than 1.0. It's actually quite straightforward - we can just try random big tests until we find one that scores more than 1.0. One might need to try several tests before that happens, and doing that using the website is slow and clumsy. However, the website actually has the code available for download (, so one can quickly craft a local stress-test and find a case that requires many attempts. Since you don't know the hidden random seed, a testcase that requires two attempts on your machine might still be solvable in one on the server, but if you find a testcase that needs ten attempts, chances are your score on the server will be more than 1.0, too.

Sunday, September 14, 2014

This week in competitive programming

There were no regular competitions this week, so it's a good time to return to a past problem.

Let's talk about TopCoder Open 2014 Round 3A hard problem "PlumbersCoins" (previous post).

In short, the problem statement is: you are given at most 50 interesting points on a line that you need to visit in any order starting from point 0. In addition to moving along the line at one unit per second, you can use teleports between the given pairs of locations. The teleports are non-interleaving (if one teleport connects points a < b, and the other connects points c < d, then either b < c or d < a), and there are at most 25 teleports, each taking exactly one second to use. What's the shortest time required to visit all interesting points?

During the competition, I didn't notice that the teleports are non-interleaving, and thus the problem became much harder. The only thing I could come up with was reducing the problem to the Traveling Salesman problem, so I coded a heuristic solution for the Traveling Salesman problem that I remembered from IOI 2002 practice problem "red": start with a random path and repeatedly reverse its subpaths while the solution improves, then repeat everything until we run out of time. Surprisingly, this solution passed the system tests!

But then I started to think: is this really surprising? Does there exist a valid testcase that makes this solution fail?

I'm relying on you to find out :) Here's a website where you can try your testcases:

Please remember to sign in at the bottom of the page to be included in the scoreboard (and so that others can't see your last testcase :))