A speaking week

Before I switch to the Mar 6 - Mar 12 week, let me correct a mistake in my previous summary: there was in fact a Codeforces round on Sunday, March 5 - but it somehow disappeared from clist.by, and my memory turned out to be too short :)

Codeforces Round 403 was the forgotten round (problems, results, top 5 on the left, analysis). Right after the round, I was sure that I needed a lot more debugging to get the last problem accepted - but it turned out that I was super close: the only issue was the often forgotten case of a=0 when solving a quadratic inequality ax²+bx+c<=0. In absence of people solving the last problem during the round it was the speed on the first five that mattered, and V--o_o--V was the quickest - congratulations!

Now we can go back to the subject week. Early on Friday, TopCoder SRM 710 took place (problems, results, top 5 on the left, analysis). Just like the previous round, the hardest problem did not budge, and the round was decided on the first two. Congratulations to al13n on the victory!

And finally, AtCoder held its Grand Contest 011 on Sunday (problems, results, top 5 on the left, my screencast with commentary, analysis). Egor has won the contest thanks to a superior strategy, as he went for the hardest problem in the last minutes of the contest instead of the second hardest. Well done!

I have attempted something new for this round: in addition to the screen content, I've included a camera feed in the screencast, and tried to explain aloud what I'm thinking and doing. I had two big hopes when I decided to do that: that I would actually be able to come up with more polished solutions that take less time to code if I explain them aloud first, and that my mumbling will be interesting to the viewers. The results of the round show that the first hope was likely unfounded, so now I'm really curious about the second one :)

As far as problems go, let me highlight problem E. You are given a huge number n with at most 500000 (decimal) digits, and need to find the smallest number k such that n can be represented as a sum of k numbers with non-decreasing decimal representation (for example, 1157888).

Thanks for reading, and check back soon for the next week's contests!

An all-black week

In stark contrast to the previous week, the Feb 27 - Mar 5 week had no contests that I'd like to mention. However, we can of course still discuss the problems I mentioned in my previous summary.

The AtCoder one was concerned with a square n times n matrix with each cell either black or white. In one step, you could take an arbitrary row of the matrix, and replace an arbitrary column of the matrix with the values from the chosen row. Your goal is to make all cells black. What is the minimum number of steps required to achieve that?

First, we can notice that if a certain column of the matrix is already all black, there's never a need to replace it, since it satisfies the final condition, and it's also the most optimal for other operations as the corresponding cell in all rows will be black.

Second, any other column can become all black only if we have a row that is all black. Moreover, as soon as we have a row that is all black, we should immediately start replicating it to all non-all-black columns (note that the number of non-all-black columns stays constant up to this point). So the problem has been reduced to: what is the minimum number of steps required to make one row all-black?

Now, each operation changes only one cell in each row. So if a row has k white cells, we will require at least k operations to make it all-black. Moreover, if each column has at least one black cell, then we require exactly k operations to make it all-black (since for each cell in this row we can replicate the row that has a black cell in the corresponding column). We can iterate over all rows and pick the one where this number is minimized. So the only unsolved case is when there's one or more all-white columns.

For each all-white column, we need at least one operation to put at least one black cell in it. If the column corresponding to the row we're making all-black has at least one black cell, then we have a row which serves two purposes: when replicating it to an all-white column, we both make it not-all-white, and also put a black cell in the row we're making all-black, so in that case no extra move is needed and we can still make the row all-black in exactly k operations.

Now, the very specific remaining case is: we want to make a certain row all-black, and the corresponding column is initially all-white. Then if we look at the first move that replaces this column, it's clear that the cell on the intersection of the all-black-to-be row and this column will stay white, meaning that we waste 1 move and require at least k+1 operation to make the row all-black. But it's easy to waste exactly one move: we just replicate any non-all-white row to the problematic column as the first move. Of course, if the board is initially all-white then there's no solution.

That completes the solution for this problem. As you can see, each particular step is relatively straightforward and not very hard to come up with. However, one has to stitch together quite a few of those, and that's where the difficulty - and beauty - of this problem lies.

The Open Cup problem was concerned with a permutation of size n. For each number, we can compute its radius: the largest number r such that r numbers to the left of our number, and r numbers to the right of our number, are all smaller than that number. For example, for the permutation "1 3 2 6 4 5" the radii are "0 1 0 2 0 0". Given the sequence of radii, how many different permutations correspond to it?

The solution depends on one main insight: let's look for n (the largest number) in the permutation. Since it is the largest number, it "stops" all other radii, and thus the problem decomposes into two independent problems to the left and to the right of this number. Just this idea leads to a O(n³) dynamic programming solution which solves the problem for each segment and tries all positions of the largest number.

Since this was a tiny bit too slow, one needed to optimize this approach. Since the radius of the largest number always reaches either to the left or to the right boundary, and no other radius should cover the largest number, in each segment there are at most two candidates for the largest number: the rightmost position with radius reaching the left boundary, and the leftmost position with radius reaching the right boundary. Since now we have just 2 candidates to check for each segment instead of n, the solution works in O(n²) which is fast enough.

Thanks for reading, and check back soon for the next week's summary!