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!