A moejy0viiiiiv week

Last week's contests started with Codeforces Round 406 on Thursday (problems, results, top 5 on the left, analysis). Quite surprisingly, this time the winning strategy involved going with the cheaper problem in the end instead of the more expensive one, although that might have involved squeezing through a solution that was not supposed to pass :) Nevertheless, congratulations to moejy0viiiiiv on his amazing non-asymptotic optimization skills!

TopCoder SRM 711 took place on Saturday (problems, results, top 5 on the left, my screencast). This time I've recorded the usual silent screencast, but it didn't seem to improve my results :) There was a moment with about 30 minutes left in the coding phase when I had 1224 points, which would be enough for the second place in this SRM. However, there was quite a bit of uncertainty: the solution I've submitted for the hardest problem was theoretically O(n⁴) with n up to 300, although it seemed to behave more like O(n³) on random testcases, and even that already took 1.5 seconds.

I've tried to come up with a case where it would time out, could not do that, but it seemed very likely that such cases exist, so I've decided that the authors would see the obvious O(n⁴) approach and make sure it fails, and implemented and submitted a true O(n³) solution losing lots of points but avoiding the possible loss of all points for that problem. After the contest ended, I've submitted my possibly-O(n⁴) solution in the practice room, and guess what? It passed the system tests as well. I could have pulled a moejy0viiiiiv :)

The natural question, of course, is this: can you challenge that solution? It should be available in the practice room, submitted by me. The problemsetter mentions a possible idea that could make this solution fail, but I'm wondering if it actually fails in practice.

I should also mention that even without the resubmission I could not challenge rng_58 for the first place, and his solution for that problem was O(n³) from the start. Congratulations on the well-deserved victory!

Here's the actual problem I've talked so much about. You are given 300 trees on the same set of 300 vertices. You want to pick exactly one edge in each tree, remove those, then add the edge you removed from i-th tree to the (i+1)-th tree, for all i (the edge from the last tree is added to the first one), in such a way that the resulting graphs are still trees. How many ways are there to do that, modulo 10⁹+7?

Open Cup 2016-17 Grand Prix of Poland has wrapped up the week on Sunday (results, top 5 on the left). Makoto continued to be on fire, winning a team contest right after winning the individual one on Saturday. Congratulations again!

This round had several nice problems, but if I have to pick one, it would be problem C. You are given a directed acyclic graph with 200000 vertices and 500000 arcs. We're going to remove one of its arcs. For each vertex v of the graph, you have to answer a question: is it true that v is guaranteed to be reachable from vertex 1, no matter which arc we remove?

In my previous summary, I have mentioned a Codeforces problem. You are given a grid with two rows and n columns, each cell containing a (not necessarily positive) integer. Your goal is to find as many non-intersecting rectangles on this grid as possible, such that each rectangle has a sum of 0. n is up to 300000.

First, we can find all rectangles with zero sum. Of course, there might be too many of those, but we can notice that for each "type" of rectangle (row 1, row 2, or both rows) we can find the partial sums from column 0 to column i, and a zero-sum rectangle corresponds to two equal partial sums, and since in the maximum answer there would never be a rectangle that can be split into two, we only need to consider pairing each partial sum with one previous occurrence of the same value, and thus have at most n useful rectangles per type, at most one ending in each column.

That observation yields a straightforward O(n²) dynamic programming solution: we'll compute a_ij - the maximum number of rectangles that we can choose in the first i cells of the first row, and in the first j cells of the second row. In order to compute this value, we consider whether we take the single-row rectangles ending in columns i and j, and also the double-row rectangle in case i=j. But O(n²) is obviously too slow with n=300000, so how to speed this up further?

The next idea is based on the fact that we currently have too much leeway in constructing the optimal solution. Whenever we pick the single-row rectangles between two double-row ones, we can pick them in any order, and the current solution effectively considers all such ways. But let's assume we always pick them "from right to left": if our current state is (i,j) and i>j, then we'll consider what happens with cell i in the first row, and if i<j, we'll consider what happens with cell j in the second row. If we do that, then the states that are important for computing the final answer have a peculiar property: if i<j, then a_jj-1<=a_ij<=a_jj (and similar for i>j), because if a_ij<=a_jj-2, we could have skipped the last rectangle we took in the first row (that led us to i), and get a better answer.

Because of this, we just need to compute the "diagonal" a_jj of the matrix, and also for each j find the smallest i that a_ij is still equal to a_jj, and the smallest i that that a_ji is still equal to a_jj, which we can do with binary search to obtain a O(nlogn) solution.

Finally, please note that Google Code Jam 2017 is just around the corner - the qualification round starts on April 7! I'm setting some of the problems this year, and I hope you'll find them interesting.