Hi everyone!
Today I want to write about the Gale-Ryser Theorem and some of its applications.
Gale-Ryser Theorem
We have an array of $$$n$$$ non-negative integers $$$a_1, a_2, \ldots, a_n$$$ and an array of $$$m$$$ positive integers $$$b_1, b_2, \ldots, b_m$$$, $$$b_i \le n$$$. The array $$$b$$$ describes a sequence of operations, in the $$$i$$$-th operation we need to decrease the values at $$$b_i$$$ positions by $$$1$$$, formally pick $$$b_i$$$ unique indices $$$j_1, j_2, \ldots, j_{b_i}$$$ and decrease $$$a_{j_p}$$$ by $$$1$$$ for $$$1 \le p \le b_i$$$. We want to know if it's possible to have all $$$a_i \ge 0$$$ after the operations.
Without loss of generality $$$b_1 \ge b_2 \ge \ldots \ge b_m$$$. The Theorem says that it's possible iff $$$\sum \limits_{i=1}^k \min(a_i, k) \ge \sum \limits_{j=1}^k b_j$$$ for $$$\forall 1 \le k \le m$$$.
NecessityIf 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 consider $$$k$$$ operations, each $$$a_i$$$ cannot contribute more than $$$k$$$ times, we can replace it by $$$\min(a_i, k)$$$. And then we check that the sum is still at least the sum of $$$b$$$. The assumption 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.
SufficiencyProof by inductionWe proceed by induction on $$$m$$$. Base case $$$m = 1$$$ is trivial. We decrease $$$b_1$$$ maximum positions and show that all the inequalities would still hold for the new array $$$a'$$$ and the array $$$b_2, b_3, \ldots, b_m$$$.
Let's verify every inequality for $$$2 \le k \le m$$$.
Assume $$$a$$$ is sorted in non-increasing order, then after we do the first operation the inequality would look like this:
$$$\sum \limits_{i=1}^{b_1} \min(a_i - 1, k - 1) + \sum \limits_{i=b_1 + 1}^{n} \min(a_i, k - 1) \ge \sum \limits_{j=2}^k b_j$$$
$$$\sum \limits_{i=1}^{b_1} \min(a_i, k) - b_1 + \sum \limits_{i=b_1 + 1}^{n} \min(a_i, k - 1) \ge \sum \limits_{j=2}^k b_j$$$
$$$\sum \limits_{i=1}^{b_1} \min(a_i, k) + \sum \limits_{i=b_1 + 1}^{n} \min(a_i, k - 1) \ge \sum \limits_{j=1}^k b_j$$$
First case — $$$a_{b_1 + 1} \lt k$$$. Then the sum hasn't changed from the initial.
Second case — $$$a_{b_1 + 1} \ge k$$$. Then $$$a_{b_1} \ge k$$$, so $$$\sum \limits_{i=1}^{b_1} \min(k, a_i) = k \cdot b_1 \ge \sum \limits_{j=1}^k b_j$$$ since $$$b_1$$$ is the maximum value.
So after doing the first operation the condition doesn't fail and the induction transition is complete.
Proof by mincutWe can phrase this task in terms of a max-flow problem. We have two parts $$$A$$$ and $$$B$$$. For $$$v \in A$$$ we draw an edge $$$S \rightarrow v$$$ with capacity $$$a_v$$$. For $$$u \in B$$$ we draw an edge $$$u \rightarrow T$$$ with capacity $$$b_u$$$. For $$$v \in A, u \in B$$$ we draw an edge $$$v \rightarrow u$$$ with capacity $$$1$$$.
The max-flow cannot be greater than $$$\sum b$$$, we want to find a sufficient condition for it to be equal to $$$\sum b$$$. By Max-flow min-cut theorem max-flow = min-cut. Consider an $$$S \backslash T$$$ cut. Split $$$A$$$ and $$$B$$$ into $$$AS, AT, BS, BT$$$ $$$(AS = A \bigcap S, AT = A \bigcap T, BS = B \bigcap S, BT = B \bigcap T)$$$. Then $$$cut = \sum \limits_{v \in AT} a_v + \sum \limits_{u \in BS} b_u + AS \cdot BT$$$. Let's fix the size of $$$BT$$$ and call it $$$k$$$. Among all cuts where $$$|BT| = k$$$ we want to find the minimal and compare it to $$$\sum b$$$. Since all terms that depend on $$$A$$$ don't depend on the choice of $$$BS$$$ and $$$BT$$$ if $$$|BT|$$$ is fixed, we can add $$$m - k$$$ minimum elements of $$$b$$$ to $$$BS$$$ and $$$k$$$ maximum elements in $$$BT$$$. Then for each $$$a_i$$$ we can either add it to $$$AT$$$ and add $$$a_i$$$ to mincut or add to $$$AS$$$ and add $$$k$$$ to mincut. So essentially mincut is increased by $$$\min(k, a_i)$$$.
So, $$$mincut_k = \sum \limits_{v \in A} \min(k, a_i) + \sum \limits_{j=k+1}^{m} b_j$$$. Since we want to show that mincut is at least $$$\sum b$$$, $$$mincut_k \ge \sum b$$$ for $$$\forall k$$$.
$$$\sum \limits_{i=1}^n \min(k, a_i) + \sum \limits_{j=k+1}^{m} b_j \ge \sum \limits_{j=1}^m b_j$$$
$$$\sum \limits_{i=1}^n \min(k, a_i) \ge \sum \limits_{j=1}^k b_j$$$
Proof by induction also suggests a strategy for the construction, which turns out to be the natural greedy strategy — always selecting $$$b_i$$$ maximum positions. Now you know the proof behind this greedy. While it doesn't follow from this proof, it's actually not needed to sort $$$b$$$ to run the greedy. Later in the blog it will also be proven, but for now simply note that we can pick maximum positions in any order we want.
An important special case, all $$$b_i = t$$$. That is, in each of $$$m$$$ operations times $$$t$$$ positions are decreased. Then it is only needed to check that $$$\sum \limits_{i=1}^n \min(t, a_i) \ge mt$$$
ProofConsider 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$$$. The sum of the differences of the minima 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)$$$.
Problem from AtCoder ABC which uses the Theorem
Another example is 1774B - Coloring. Here's the short statement: we have $$$n$$$ cells and $$$m$$$ colors, each cell must be colored. For each color there must be exactly $$$a_i$$$ cells painted with that color ($$$\sum a = n$$$). Also, every window of given size $$$k$$$ cannot have cells of one color.
Solution (yes, editorial for div2B)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 two conditions we need to check, for the first $$$\lfloor \frac{n}{k} \rfloor$$$ operations and for all of them.
$$$\sum \limits_{i=1}^m \min(\lfloor \frac{n}{k} \rfloor, a_i) \ge n - n \mod k$$$
$$$\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.
Here is a problem where you can try applying the idea yourself 1893D - Colorful Constructive
Dual
There is also a dual version of this problem. Suppose on each operation we decrease at most $$$b_i$$$ elements by $$$1$$$, but the goal now is to get all $$$a_i = 0$$$. Just swap $$$a$$$ and $$$b$$$ and we'll get the same problem as before! Originally all $$$b_j$$$ required $$$b_j$$$ positions in $$$a$$$ and each position $$$a_i$$$ could've been picked at most $$$a_i$$$ times. And here each $$$a_i$$$ must be picked exactly $$$a_i$$$ times (we need to pick exactly $$$a_i$$$ positions in $$$b$$$) and each $$$b_j$$$ can be picked at most $$$b_j$$$ times.
Sometimes all of the operations are the same. Usually in this case we want to find the minimum number of operations $$$m$$$ which we need to make all $$$a_i = 0$$$. Suppose all operations decrease at most $$$t$$$ positions. How do we find the $$$m$$$?
SolutionWe have
$$$\sum \limits_{i=1}^m min(k, b_i) \ge \sum \limits_{i=1}^k a_i$$$.
Since all $$$b_i = t$$$, this becomes
$$$m \cdot min(k, t) \ge \sum \limits_{i=1}^k a_i$$$.
For $$$k \le t$$$, this gives $$$km \ge \sum \limits_{i=1}^k a_i$$$. In particular, for $$$k = 1$$$ we obtain $$$m \ge a_1$$$, and since $$$a_1 \ge a_i$$$, this inequality also implies $$$km \ge ka_1 \ge \sum \limits_{i=1}^k a_i$$$ for every $$$k \le t$$$.
For $$$k \gt t$$$ the left-hand side is always $$$tm$$$, while the right-hand side increases till $$$\sum a$$$. Hence it suffices to check only $$$k = 1$$$ and $$$k = n$$$ to find minimal $$$m$$$.
$$$k = 1$$$. $$$m \ge a_1$$$
$$$k = n$$$. $$$tm \ge \sum a \Rightarrow m \ge \lceil \frac{\sum a}{t} \rceil$$$
Therefore $$$m = \max(a_1, \lceil \frac{\sum a}{t} \rceil)$$$.
Right now I can only remember this problem 2181G - Greta's Game, which uses this fact, but this idea appears sometimes, usually where $$$t = 2$$$.
Also an application of this idea in Meta Hacker Cup, problem B
Lastly, there is a problem from Open Olympiad 24-25 XIX Open Olympiad in Informatics - Final Stage, Day 2 (Unrated, Online Mirror, IOI rules), which motivated me to understand this theorem. The fact below is crucial for the solution, so it's under a spoiler as well.
Fact - The greedy algorithm to always decrease maximums produces the lexicographically largest possible sorted array among all arrays which are achievable with the operations. The proof also doesn't use the fact that the operations are done in non-increasing order, so the greedy produces the same array for every order of operations.
ProofWithout loss of generality array $$$a$$$ is sorted in non-decreasing order and operations decrease maximums in such a way that the array remains sorted (it's always possible to do that, when there are two positions with the same value we first decrease the left one).
Denote the array which is produced by the greedy algorithm as $$$b$$$. I want to show, that for every $$$t$$$ $$$\sum \limits_{i=1}^t b_i \ge \sum \limits_{i=1}^t c_i$$$ for every array $$$c$$$ which can be produced by the operations. Let's prove that by contradiction.
Suppose there's a sequence of operations which maximizes every single prefix sum in the resulting array $$$b$$$ but it has bad operations. Operation is bad iff there is a pair of indices $$$i, j$$$ such that $$$a_i \lt a_j$$$ (which also means that $$$i \lt j$$$) and $$$a_i$$$ was decreased and $$$a_j$$$ wasn't. Let's look at the last bad operation and a pair of the indices $$$i, j$$$ mentioned above. If $$$b_i \lt b_j$$$, then we can decrease $$$a_j$$$ instead of $$$a_i$$$ and we will increase prefix sums from $$$i$$$ to $$$j - 1$$$, contradiction. So $$$b_i = b_j$$$. Then somewhere later in the sequence of operations there is one that decreases $$$a_j$$$ and not $$$a_i$$$. Let's swap $$$i$$$ and $$$j$$$ in both operations. Then $$$b$$$ hasn't changed, but if we write down the indices for each operation (in increasing order) for every operation from first to last, then the sequence is lexicographically greater. Since there is a finite number of such sequences, the process will terminate. When it does, no operation is bad, otherwise we could've increased the sequence.
That proves that the greedy algorithm produces an array such that every prefix sum is maximized. That also means, that the array itself is lexicographically maximal.
