Gale-Ryser Theorem

If we can do all operations and all $$$a_i$$$ remain non-negative, then the sum of $$$a_i$$$ is at least the sum of $$$b_j$$$ ($$$\sum a \ge \sum b$$$). Since we do $$$k$$$ operations, each $$$a_i$$$ cannot contribute more than $$$k$$$ times, we can replace it with $$$\min(a_i, k)$$$. And then we check that the sum is still at least the sum of $$$b$$$. The condition that $$$b$$$ is non-increasing is here because we want to verify the condition only for the maximal set of $$$k$$$ operations. If we can do $$$k$$$ maximal operations then we can do every other set of $$$k$$$ operations.

Condider a function $$$f(k) = \sum \limits_{i=1}^n \min(k, a_i) - kt$$$. We want to find its minimum to check if it's less than $$$0$$$.

$$$f(k + 1) - f(k) = \sum \limits_{i=1}^n \min(k + 1, a_i) - \min(k, a_i) - t$$$. Sum of differences of minimums is the number of $$$a_i \gt k$$$, which decreases with $$$k$$$, so $$$f$$$ is a concave function. That means that the minimum value is either $$$f(0)$$$ or $$$f(m)$$$. Since $$$f(0) = 0$$$ we only need to check $$$f(m)$$$.

For each window of size $$$k$$$ we choose $$$k$$$ different colors and decrease their frequency by $$$1$$$. That's exactly the process of the Theorem. The last window will have size $$$n \mod k$$$, there we put all the remaining colors. So we have operations $$$b_1 = b_2 = \ldots = b_{\lfloor \frac{n}{k} \rfloor} = k, b_{\lfloor \frac{n}{k} \rfloor} + 1 = n \mod k$$$. From the previous fact there are only $$$2$$$ conditions we need to check, for the first $$$\lfloor \frac{n}{k} \rfloor$$$ operations and for all of them.

1. $$$\sum \limits_{i=1}^m \min(\lfloor \frac{n}{k} \rfloor, a_i) \ge n - n \mod k$$$

2. $$$\sum \limits_{i=1}^m \min(\lfloor \frac{n}{k} \rfloor + 1, a_i) \ge n$$$

The first condition means that there are at most $$$n \mod k$$$ values in $$$a$$$ that are greater than $$$\lfloor \frac{n}{k} \rfloor$$$.

The second condition together with the fact that $$$\sum a = n$$$ means that $$$\max(a) \le \lfloor \frac{n}{k} \rfloor + 1$$$.

Lastly, how do we select the colors for each cell? For the first window we just pick $$$n \mod k$$$ most frequent colors and then for each window of size $$$k$$$ we first pick colors and then from left to right select any color that can be put. It works because of pigeonhole principle.

We have $$$\sum \limits_{i=1}^m min(k, b_i) \ge \sum \limits_{i=1}^k a_i$$$.

$$$m \cdot min(k, 2) \ge \sum \limits_{i=1}^k a_i$$$.

It's optimal to choose either $$$k = 1$$$ or $$$k = n$$$ to find minimal $$$m$$$.

1. $$$k = 1$$$. $$$m \ge a_1$$$

2. $$$k = n$$$. $$$2m \ge \sum a \Rightarrow m \ge \lceil \frac{\sum a}{2} \rceil$$$

So we get that $$$m = \max(a_1, \lceil \frac{\sum a}{2} \rceil)$$$.

$$$m \cdot min(k, n - 1) \ge \sum \limits_{i=1}^k a_i$$$.

1. $$$k \le n - 1$$$. $$$m \cdot k \ge \sum \limits_{i=1}^k a_i$$$. $$$k = 1 \Rightarrow m \ge a_1 \Rightarrow tm \ge t \cdot a_1 \ge \sum \limits_{i=1}^t a_i$$$

2. $$$k = n$$$. $$$m \ge \lceil \frac{\sum a}{n} \rceil$$$.

So $$$m = \max(a_1, \lceil \frac{\sum a}{n} \rceil)$$$.