Shreckless#12977

Shreckless (Editorial)

Author:

Anton Trygub

Solved by:

First to solve:

RAF 100011

Consider two adjacent columns, assume in sorted order they are a_1 \leq a_2 \leq \ldots \leq a_n and b_1 \leq b_2 \leq \ldots \leq b_n. For any permutation , what’s the maximum number of indices such that a_i>b_{p_i}? (Therefore making the corresponding row not sorted).

Let’s see how to check if we can get at least such indices. It makes sense to pair the largest elements of with smallest elements of . It’s also clear that we should be pairing them in increasing order: (a_{n-k+1}, b_1), \ldots, (a_n, b_k). Then we can get pairs iff a_{n-k + i} > b_i for all 1\leq i \leq k.

Now, we can find the largest number of such pairs we can form with binary search over . This would work in O(n\log{n}). We will denote this value by f(a, b). Denote the columns as a_1, a_2, \ldots, a_m. Clearly, we cannot make more than f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m) unsorted rows. So, if f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m) < n, the answer is NO.

It turns out that if f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m) \geq n, we can make all rows not sorted! Algorithm is very simple. Arrange elements of the -st column arbitrarily. Then, for i = 2, \ldots, m, do the following:

Assume there are sorted rows remaining (for i = 2 we have x = n). We assume largest elements of a_{i-1} are in precisely those columns (we will see why later). Now, arrange the elements of a_i as follows:

  1. Put min(x, f(a_{i-1}, a_i)) smallest elements of column a_i next to min(x, f(a_{i-1}, a_i)) largest elements of column a_{i-1}, as discussed before, making those rows not sorted.

  2. Put x - min(x, f(a_{i-1}, a_i)) largest elements of column a_i in remaining sorted rows.

  3. Put other elements arbitrarily.

This way, we will get min(n, f(a_1, a_2) + f(a_2, a_3), \ldots, f(a_{m-1}, a_m)) unsorted rows.

Runtime: O(nm\log{n})).