This week in competitive programming

2117 programmers took part in Codeforces Round 221 on Tuesday (top 5 on the left). I didn't, so I can simply share the links to problems and results, and congratulate the winner Touma_Kazusa for whom this was just the third Codeforces round!

2075 programmers took part in TopCoder SRM 602 on Saturday (problems, results, my screencast, top 5 on the left). The 250 problem was simple dynamic programming, the 550 was a tricky case study with simple data structures, and 1000 was a mostly mathematical problem to be solved on paper. The 550 possessed an interesting property: despite being a very tricky case study when N is up to 100000, it allowed a very simple solution when N is around 5-10 that can be implemented in just a couple of minutes. That's why after submitting it, I've implemented that simple solution and compared it against my solution on thousands of random testcases. It helped discover a silly bug and I had to resubmit losing quite a few points, but I would've lost much more had my solution failed the system test. My point is that even in very short contests, like TopCoder, there are situations for such stress-testing against a simple solution.

2493 programmers took part in Codeforces Round 222 on Sunday (problems, results, my screencast that was unfortunately truncated after about an hour when I've locked my computer, top 5 on the left). The problems were fairly standard, but the last one required a great deal of accuracy. I'd like to highlight the easiest problem, though. The task was: given a connected set of cells on the grid and a number K, remove K cells from the set so that it remains connected. It is quite straightforward and can be solved in many ways, but it still requires some logical thinking and the statement is very easy to understand. I think this is a very good easy algorithmic problem.

One other peculiar fact about this week's Codeforces rounds is: today's top 5 are all from ex-USSR, while 4 out of Tuesday's top 5 are from China and Japan. There are several possible explanations. First, Tuesday's round was 1.5 hours later so it was less convenient for people in eastern timezones. Second, top 5 in a round is so random that there's nothing to explain at all. Third, one of the round's problems might be similar to a problem from an older contest that was only popular in a certain region. But these are the boring explanations :) Wouldn't it be interesting if different styles of education present in Russia vs Japan vs China led to different sets of skills that would in turn lead to such country-specific contest results? Has anybody seen more careful analysis of country distribution in algorithmic programming contest results?

This week in competitive programming

In contrast to last week, this week was quite light on programming contests. Late on Saturday, the final online round of the Facebook Hacker Cup took place (my screencast, top 5 on the left). Several things went wrong at the same time for me. First, I've spent an hour on the easiest problem by making a somewhat classical mistake: the problem statement had a constraint n_i<=4, and I immediately started thinking about solutions that rely on that constraint. It turned out that the correct solution works fine even for large values of n, and is much, much simpler that what I came up with during that hour. Then, I've implemented the solution for the third problem with the correct big-O asymptotic complexity, but without caring too much about the constant factor, and couldn't reduce the constant factor under the pressure of the last 30 minutes of the contest. I've made a desperate attempt to still run my solution against judges' input, but it timed out as expected.

When two problems go wrong at the same time, getting into the top 25 in the world is too hard, so congratulations and good luck to everybody who made it to the onsite finals!

On Sunday, TopCoder SRM 601 took place (problems, results, my screencast, top 5 on the left). Both the medium and the hard problems required tricky dynamic programming: the solution that comes to mind right after reading the problem has too many states in dynamic programming, so you have to somehow reduce the state space. While both problems look a bit artificial and thus not as exciting to solve, they are a good way to practice advanced dynamic programming if you want to (medium, hard).

Thanks for reading, and see you next week!

This week in competitive programming

 This week was very busy with contests. The week started with the second quaterfinal of the Kotlin challenge (problems in Russian, results in Russian, top 5 on the left). The round didn't go as smoothly as the first one, and the system had some downtime, so there will be a third quarterfinal to compensate those affected.

Then, Codeforces Round 219 took place on Friday (problems, results, top 5 on the left). Three out of four properties of an ideal contest held:
1) nobody solved all problems;
2) each problem got solved by somebody;
3) there's no problem solved by everybody.
The only missing part is
4) there's no contestant with zero problems solved.
But I guess the latter is quite hard to achieve in the Codeforces setting.

Saturday started with TopCoder SRM 600 which featured a T-shirt giveaway because of the round number (problems, results, my screencast, top 5 on the left). The screencast features two very long and probably boring situations: first, for the last 20 minutes of the coding phase I couldn't understand why my solution doesn't pass one of the samples, but couldn't. It turned out I was missing the fact that two lines can intersect in a point with non-integer coordinates, and it's unclear to me now how one can ignore this fact for so long. But even more disturbingly, during the last 13 minutes of the challenge phase I couldn't come up with a testcase for the medium problem with answer zero, but where there's exactly one way to reach zero. There's really no excuse for that.

Later that day, the second round of Facebook Hacker Cup happened (my screencast, top 5 on the left). With the format of competition penalizing very heavily for one's mistakes, the right strategy seemed to be to write two solutions for each problem, one fast and one slow, and compare them on many small testcases to make sure the fast solution is correct. That plan worked out well - but one may wonder if that strategy would be too slow to get into the top 25 in Round 3.

Just about 8 hours after the end of the Hacker Cup, on Sunday, the next stage of the Open Cup took place (top 5 on the left). The problems turned out to be too easy and the winner solved all of them in just over 2 hours. One must note the performance of the second-placed XZ team: I believe this is the first full team (as opposed to teams of just one person) regularly participating in the Open Cup from the Bay Area and from the USA in general. The convex hull of all participating teams on the globe (is there even such a thing on a sphere?..) just got bigger.

Later on Sunday, TopCoder SRM 600.5 took place (problems, results, top 5 on the left). It was a very unusual match, with 4 hours of coding and second and third problems being harder than the usual 'hard' problems from TopCoder. However, only those two problems got solved, with the grand total of 10 accepted submissions for about a thousand contestants and 4 hours.

The third problem was amazingly simply stated, and I still have no idea how to solve it (full problem statement). You are given a graph with N vertices numbered from 1 to N, where vertices A and B are connected by an edge if and only if abs(A-B) is in the given set S. How many connected components are there in this graph? N is up to 10¹⁸, S has up to 50 elements, each up to N. Any ideas?

Let me finish this very long post with a non-scoreboard picture, taken in Barcelona which I visited for 4 days and where I've solved most of the contests mentioned above:

The decisive TopCoder Open finals hard problem

Let me remind you the hardest problem from this year's TCO finals (link to full problem statement): you are given a NxN (N<=50) grid with some cells black and some cells white. How many ways are there to place non-intersecting T-tetraminoes onto the grid such that each "central" cell of a tetramino falls onto a white cell, and each white cell is the central cell of some tetramino? You need to find this number in O(N^2).

TopCoder has published a great editorial which you can consult for more details, but I want to share an approach that is a bit different. First, we can notice that if a white cell is on the border of the field, then the corresponding tetramino can be placed immediately in exactly one way. If, after placing such tetraminoes, we find a white cell that has one of its adjacent cells already covered, we can also place the corresponding tetramino (see the picture for an example of such deterministic placement, white cells are denoted with circles). Finally, if two white cells are adjacent, we can also place the two corresponding tetraminoes. We can repeat this process until we either arrive at a contradiction, in which case we have zero solutions, or there are no more 'deterministic' tetraminoes left.

In the second case, let's consider the graph formed by the edges connecting the white cells to four neighboring black cells. It's not hard to see that its connected components can be handled separately, with the final result obtained by multiplication. When a connected component is a tree, then exactly one black cell in this connected component will remain empty (because it has 3K+1 black cells and K white cells, for example the picture on the left has 13 black and 4 white cells), and it's not hard to see that we can pick any black cell to be empty, after which the positioning of all tetraminoes is determined similarly to the "tetramino on the border" case, so we have 3K+1 solutions here.

Finally, when a connected component contains a cycle, then there are two ways to place the tetraminoes along that cycle, and all remaining tetraminoes are then placed deterministically. In case a connected component has more than one cycle, in other words the number of edges more than the number of vertices, there will be no solution (for example because the number of black cells will be fewer than 3K).

This week in competitive programming

The weekdays featured just one contest, TopCoder SRM 599 on Wednesday (problems, results, top 5 on the left, my screencast). The hard problem was: you are given a directed graph with at most 50 vertices and at most 8 edges (so most vertices don't have any adjacent edges at all), and a rooted tree with the same number of vertices. How many ways are there to map the vertices of the graph to the vertices of the tree (one-to-one) such that each edge of the graph corresponds to ancestor-descendant pair in the tree? One funny aspect of this problem is the complexity of the solution. If 50 is N and 8 is M, then the expected solution complexity was O(N*5^M), the solution that the authors were trying to fail was O(N*9^M) (more details from the problem author at Codeforces), and I've managed to come up with a O(N*7^M) solution they didn't expect, and barely squeeze in the time limit.

The weekend featured elimination rounds for two annual contests. On Saturday, the first official round of the Kotlin Challenge took place (problems, results, top 5 on the left). This is a brand new competition with problems in Russian, final round in St Petersburg in April 2014, and only one allowed programming language - Kotlin. I'm pretty sure almost all contestants at the top of the scoreboard didn't know the language before, but it appears that it's conventional enough and learning to do simple things using it is not hard. Even if you missed this round, you still have a chance to register and participate in the next round this Wednesday, but keep in mind that all tasks and judges communication is in Russian.

For 24 hours between Saturday and Sunday, the first round of the Facebook Hacker Cup took place. Since they don't publish the problems and the scoreboard, I assume they don't want to encourage discussion so I won't go deeper here :)

Thanks for reading, and see you next week!

This week in competitive programming

The week started with Codeforces Round 215 on Tuesday (problems, results, top 5 on the left, my screencast). The round was unusually easy, with many competitors solving all five problems around the 1 hour mark, and the round was decided on challenges. There were two main strategies that could give one hundreds of challenge points. First, there was a nasty integer overflow possible in problem B, so a carefully constructed testcase could either make many solutions time out or make them produce a wrong answer. Then, problem C was to be essentially solved on paper, and asked to find some simple function f(n), so it was very easy to check this function in other solutions to see if it's any different from the correct one. Egor employed both strategies and achieved a commanding win, over 200 points above the second place.

On Friday, TopCoder Single Round Match 598 took place (problems, results, top 5 on the left). I didn't take part, so I can only admire Egor's second victory of the week. Another interesting fact is that the SRM took place at 6am Russian time, but the 4th and 5th place were taken by members of SPb SU 4 and SPb ITMO 1, two teams due to compete in NEERC just two days later - apparently they thought that additional preparation is worth more than not waking up early.

Did that work out? You can see the NEERC top 5 on the left (problems, results). SPb SU 4 won as expected, although they couldn't solve any of the 3 difficult problems, so they could easily lose the first place to another team. SPb ITMO 1 didn't do as good, but still qualified for the World Finals. Speaking of World Finals qualifications, in case NEERC competitors read my blog, it has just been announced that the ACM ICPC headquarters have agreed to give 17th slot to NEERC teams, so the Moscow Institute of Steel and Alloys is also going to the World Finals (all finalists from NEERC)!

As I mentioned before, I've test-solved this contest, my result was 9 problems. Out of the three difficult problems I've solved problem D, and I find it very beautiful. The author of this problem is Egor, so this seems to be his good week :)

Here's how it goes: you are given 50 strings of length at most 10. You need to construct a rooted tree and write exactly one character on each edge of the tree, in such a way that one can find each of those 50 strings in this tree. We say that we can find a string in such tree if we obtain this string using the following process. Start at some vertex, and repeat the following: pick one of the children of the current vertex (remember, the tree is rooted), write down the character from that child's edge, and make that child the new current vertex. In other words, there needs to be a path from some vertex in the tree to another vertex in the tree that always goes away from the root and has the string written along it (see the PDF for the complete statement, look for problem D "Dictionary"). What is the minimum possible size of such tree?

NEERC 2013

There's roughly 10 minutes left before the start of NEERC 2013, one of the strongest ACM ICPC regional contests. The live standings will be at http://neerc.ifmo.ru/information/standings.html, a much more magical experimental scoreboard at http://ctddev.ifmo.ru/, problems at http://neerc.ifmo.ru/information/problems.pdf, live text commentary in Russian by tourist and niyaznigmatul at http://neercnews.blogspot.ru/2013/12/neerc-2013.html, Twitter comments at https://twitter.com/NEERCNews and more generally at https://twitter.com/search?q=%23NEERC&src=hash&f=realtime. Some more preview links: http://codeforces.com/blog/entry/9784, http://codeforces.ru/blog/entry/9754, http://neerc2013.snarknews.info/, http://srv.snarknews.info/~ejudge/showvote.cgi?data=neerc2013.

I've test-solved the contest several days ago, and it has awesome problems of different types, so hopefully each team will find something it likes and we'll see a fierce competition. Good luck to all contestants!