_This blog is a submission for the [Third Codeforces Month of Blog Posts](https://codeforces.me/blog/entry/149422), thanks to [user:cadmiumky,2026-02-10] for the initiative!_↵
↵
_Thanks to [user:TeaTime,2026-02-10] and [user:k1r1t0,2026-02-10] for giving feedback on the post._↵
↵
---↵
↵
Hi everyone!↵
↵
I want to talk about Gale-Ryser Theorem and some of its applications. I've provided proofs for each fact in the blog, they're hidden under the spoilers.↵
↵
---↵
↵
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$.↵
↵
<spoiler summary="Necessity">↵
↵
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 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.↵
↵
</spoiler>↵
↵
<spoiler summary="Sufficiency">↵
↵
<spoiler summary="Proof by induction">↵
↵
We 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} < 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.↵
</spoiler>↵
↵
↵
<spoiler summary="Proof by mincut">↵
↵
We 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$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
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. However, the proof by induction requires us to do the operations in decreasing order. While it doesn't follow from this proof, it's actually not needed to sort $b$ to run the greedy. In other words, the order of operations doesn't matter, if we always pick only the maximum positions.↵
↵
<spoiler summary="Proof that order of operations doesn't matter">↵
To show that, I want to prove that swapping two adjacent operations $k_1$ and $k_2$ is possible. if $k_1 = k_2$, it's trivial. Then, without loss of generality, $k_1 > k_2$.↵
↵
Assume the array $a$ is sorted. The operations will decrease such positions that the array remains sorted. In order to do that, we pick positions from greater values left to right. For example, the red $8$ positions in this array would be picked.↵
↵
$[1, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6, 7, 8, 8]$↵
↵
$[1, 2, 3, 3, \color{red}{4}, \color{red}{4}, 4, 4, 4, 4, \color{red}{5}, \color{red}{5}, \color{red}{6}, \color{red}{7}, \color{red}{8}, \color{red}{8}]$↵
↵
Notice that an operation decreases some suffix and some prefix of the next value. Also, this is the only way to remain the array sorted.↵
↵
We show that the multiset of indices selected by the $k_1$ and $k_2$ operations is the same regardless of whether $k_1$ is applied before $k_2$ or $k_2$ before $k_1$. Since there is no ambiguity in the choice of positions, we can actually only look at the number of positions with a certain value that were decreased zero, once or twice.↵
↵
Denote $c_x$ as the frequency of $x$ in the array $a$.↵
↵
Let's start with a simple case where the first operations only decreases the maximum value $x$. If $k_1 + k_2 \le c_x$, then the first $k_1 + k_2$ positions where $x$ is will be decreased. if $k_1 + k_2 \ge c_x$, then:↵
↵
- If we apply $k_1$ first and then $k_2$, the first operation decreases $k_1$ entries equal to $x$. The second operation decreases the remaining $c_x - k_1$ entries equal to $x$, and then decreases entries equal to $x-1$ (some of which may have been equal to $x$ before applying $k_1$). Crucially, after applying $k_1$ there are at least $k_1$ occurrences of $x-1$, so the $k_2$ operation only affects values equal to $x$ or $x-1$. Consequently, all entries equal to $x$ become $x-1$, and exactly $k_2 - (c_x - k_1) = k_1 + k_2 - c_x$ entries equal to $x-1$ are further decreased.↵
↵
- If we apply $k_2$ first and then $k_1$, the first operation decreases $k_2$ entries equal to $x$. The second operation decreases the remaining $c_x - k_2$ entries equal to $x$, and then decreases $k_1 + k_2 - c_x \le k_2$ entries equal to $x-1$. The inequality ensures that no other values are affected. Again, all entries equal to $x$ become $x-1$, and exactly $k_1 + k_2 - c_x$ entries equal to $x-1$ are decreased.↵
↵
Now consider the more general case where $x$ is the maximum number such that $c_x + c_{x+1} + \ldots > k_1$. If no such $x$ exists, then $k_1 = n$, which means that all numbers are decreased by $1$ and the order of indices which we choose for $k_2$ won't change, so the swap of operations doesn't affect the resulting array.↵
↵
Otherwise the first operation $k_1$ would look like this:↵
↵
↵
↵
Red stripes show the positions that are decreased. We can split the array $a$ in four parts: $<x$, $x$, $x+1$, $>x+1$ (some of them, but not $x$, might be empty). Denote the number of decreased $x$-s as $L$ and the number of elements in the fourth part as $R$. As was mentioned before, the operation decreases some suffix and some prefix of entries of the number before it.↵
↵
Assume $k_2 \le R$. Let's look at the sets of positions which $k_2$ would decrease if it's the first and if it's the second operation. They are the same, since the order, in which we pick indices, of the $R$ positions doesn't change after applying $k_1$ first, as it decreases all values in that suffix and all entries of the value before. On the other hand the sets of positions which $k_1$ would decrease are also the same. In both cases the number of elements that are greater than $x$ is the same and less than $k_1$, so all of them will be decreased. The remaining prefix is unaffected by $k_2$, so the order of positions chosen in the prefix is also the same.↵
↵
Now let's look at another case, where $k_2 > R$. I claim that the last $R$ elements will be decreased twice, hence can be ignored.↵
↵
- first $k_1$ then $k_2$ — $k_1$ doesn't change the order of the first $R$ indices which are then chosen by $k_2$.↵
↵
- first $k_2$ then $k_1$ — $k_2$ doesn't change the number of elements that are greater than $x$, so $k_1$ will decrease all of them, including all positions in $R$.↵
↵
Now the problem reduces to $k_1$ decreasing only two distinct values. Once again, there are two cases.↵
↵
1. $k_2 \le c_{x+1}$. Then let's look at the amount of entries of each value that will be decreased.↵
↵
- first $k_1$ then $k_2$ — $k_1$ will decrease $c_{x+1}$ entries of $x+1$ and $k_1 - c_{x+1}$ entries of $x$. $k_2$ will then decrease $k_2$ entries of $x$, since $c_{x+1} \ge k_2$.↵
↵
- first $k_2$ then $k_1$ — $k_2$ will decrease $k_2$ entries of $x+1$. $k_1$ will decrease $c_{x+1} - k_2$ entries of $x+1$ and $k_1 + k_2 - c_{x+1} < c_x + k_2$ entries of $x$. The inequality shows that $k_1$ will only decrease entries of $x$ and $x+1$.↵
↵
2. $k_2 > c_{x+1}$. This case is tedious as there are subcases with $x - 1$, but the logic is the same, so I leave it as an exercise to the reader :)↵
↵
Therefore, in all cases both orders of operations result in the same array, so we can swap adjacent operations without any effect. And if we can swap adjacent operations, we can get any permutation of operations we want.↵
↵
</spoiler>↵
↵
---↵
↵
Tasks for practice↵
------------------↵
↵
[Problem from AtCoder ABC](https://atcoder.jp/contests/abc424/tasks/abc424_g)↵
↵
[Problem from JOISC 2023](https://qoj.ac/contest/1210/problem/6339)↵
↵
---↵
↵
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$↵
↵
<spoiler summary="Proof">↵
Consider 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 > 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)$.↵
</spoiler>↵
↵
Another example is [problem:1774B]. 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.↵
↵
<spoiler summary="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.↵
↵
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 (there are more allowed colors we can put than the number of banned colors).↵
</spoiler>↵
↵
Here is a problem where you can try applying the idea yourself [problem:1893D]↵
↵
---↵
↵
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$?↵
↵
<spoiler summary="Solution">↵
↵
We 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 > 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$.↵
↵
1. $k = 1$. $m \ge a_1$↵
↵
2. $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)$.↵
↵
</spoiler>↵
↵
Right now I can only remember this problem [problem:2181G], 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](https://www.facebook.com/codingcompetitions/hacker-cup/2025/round-2/problems/B)↵
↵
---↵
↵
Lastly, there is problem D2 from Open Olympiad 24-25 day 2 [contest:2080], which motivated me to understand this theorem. The fact below is crucial for the solution, so it's under a spoiler as well.↵
↵
<spoiler summary="Fact">↵
↵
1. The greedy algorithm to always decrease maximums produces the lexicographically largest possible sorted array among all arrays which are achievable with the operations.↵
↵
<spoiler summary="Proof">↵
Without loss of generality array $a$ is sorted in non-decreasing order and operations decrease maximums in such a way that the array remains sorted.↵
↵
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 < a_j$ (which also means that $i < 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 < 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 if we fix the order of operations, then the operations which pick maximums produce an array with maximal prefix sums. In that case the order of operations doesn't matter, so we'll always get the same array no matter what initial order we've chosen.↵
</spoiler>↵
↵
</spoiler>↵
↵
↵
_Thanks to [user:TeaTime,2026-02-10] and [user:k1r1t0,2026-02-10] for giving feedback on the post._↵
↵
---↵
↵
Hi everyone!↵
↵
I want to talk about Gale-Ryser Theorem and some of its applications. I've provided proofs for each fact in the blog, they're hidden under the spoilers.↵
↵
---↵
↵
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$.↵
↵
<spoiler summary="Necessity">↵
↵
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 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.↵
↵
</spoiler>↵
↵
<spoiler summary="Sufficiency">↵
↵
<spoiler summary="Proof by induction">↵
↵
We 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} < 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.↵
</spoiler>↵
↵
↵
<spoiler summary="Proof by mincut">↵
↵
We 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$↵
↵
</spoiler>↵
↵
</spoiler>↵
↵
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. However, the proof by induction requires us to do the operations in decreasing order. While it doesn't follow from this proof, it's actually not needed to sort $b$ to run the greedy. In other words, the order of operations doesn't matter, if we always pick only the maximum positions.↵
↵
<spoiler summary="Proof that order of operations doesn't matter">↵
To show that, I want to prove that swapping two adjacent operations $k_1$ and $k_2$ is possible. if $k_1 = k_2$, it's trivial. Then, without loss of generality, $k_1 > k_2$.↵
↵
Assume the array $a$ is sorted. The operations will decrease such positions that the array remains sorted. In order to do that, we pick positions from greater values left to right. For example, the red $8$ positions in this array would be picked.↵
↵
$[1, 2, 3, 3, 4, 4, 4, 4, 4, 4, 5, 5, 6, 7, 8, 8]$↵
↵
$[1, 2, 3, 3, \color{red}{4}, \color{red}{4}, 4, 4, 4, 4, \color{red}{5}, \color{red}{5}, \color{red}{6}, \color{red}{7}, \color{red}{8}, \color{red}{8}]$↵
↵
Notice that an operation decreases some suffix and some prefix of the next value. Also, this is the only way to remain the array sorted.↵
↵
We show that the multiset of indices selected by the $k_1$ and $k_2$ operations is the same regardless of whether $k_1$ is applied before $k_2$ or $k_2$ before $k_1$. Since there is no ambiguity in the choice of positions, we can actually only look at the number of positions with a certain value that were decreased zero, once or twice.↵
↵
Denote $c_x$ as the frequency of $x$ in the array $a$.↵
↵
Let's start with a simple case where the first operations only decreases the maximum value $x$. If $k_1 + k_2 \le c_x$, then the first $k_1 + k_2$ positions where $x$ is will be decreased. if $k_1 + k_2 \ge c_x$, then:↵
↵
- If we apply $k_1$ first and then $k_2$, the first operation decreases $k_1$ entries equal to $x$. The second operation decreases the remaining $c_x - k_1$ entries equal to $x$, and then decreases entries equal to $x-1$ (some of which may have been equal to $x$ before applying $k_1$). Crucially, after applying $k_1$ there are at least $k_1$ occurrences of $x-1$, so the $k_2$ operation only affects values equal to $x$ or $x-1$. Consequently, all entries equal to $x$ become $x-1$, and exactly $k_2 - (c_x - k_1) = k_1 + k_2 - c_x$ entries equal to $x-1$ are further decreased.↵
↵
- If we apply $k_2$ first and then $k_1$, the first operation decreases $k_2$ entries equal to $x$. The second operation decreases the remaining $c_x - k_2$ entries equal to $x$, and then decreases $k_1 + k_2 - c_x \le k_2$ entries equal to $x-1$. The inequality ensures that no other values are affected. Again, all entries equal to $x$ become $x-1$, and exactly $k_1 + k_2 - c_x$ entries equal to $x-1$ are decreased.↵
↵
Now consider the more general case where $x$ is the maximum number such that $c_x + c_{x+1} + \ldots > k_1$. If no such $x$ exists, then $k_1 = n$, which means that all numbers are decreased by $1$ and the order of indices which we choose for $k_2$ won't change, so the swap of operations doesn't affect the resulting array.↵
↵
Otherwise the first operation $k_1$ would look like this:↵
↵
↵
↵
Red stripes show the positions that are decreased. We can split the array $a$ in four parts: $<x$, $x$, $x+1$, $>x+1$ (some of them, but not $x$, might be empty). Denote the number of decreased $x$-s as $L$ and the number of elements in the fourth part as $R$. As was mentioned before, the operation decreases some suffix and some prefix of entries of the number before it.↵
↵
Assume $k_2 \le R$. Let's look at the sets of positions which $k_2$ would decrease if it's the first and if it's the second operation. They are the same, since the order, in which we pick indices, of the $R$ positions doesn't change after applying $k_1$ first, as it decreases all values in that suffix and all entries of the value before. On the other hand the sets of positions which $k_1$ would decrease are also the same. In both cases the number of elements that are greater than $x$ is the same and less than $k_1$, so all of them will be decreased. The remaining prefix is unaffected by $k_2$, so the order of positions chosen in the prefix is also the same.↵
↵
Now let's look at another case, where $k_2 > R$. I claim that the last $R$ elements will be decreased twice, hence can be ignored.↵
↵
- first $k_1$ then $k_2$ — $k_1$ doesn't change the order of the first $R$ indices which are then chosen by $k_2$.↵
↵
- first $k_2$ then $k_1$ — $k_2$ doesn't change the number of elements that are greater than $x$, so $k_1$ will decrease all of them, including all positions in $R$.↵
↵
Now the problem reduces to $k_1$ decreasing only two distinct values. Once again, there are two cases.↵
↵
1. $k_2 \le c_{x+1}$. Then let's look at the amount of entries of each value that will be decreased.↵
↵
- first $k_1$ then $k_2$ — $k_1$ will decrease $c_{x+1}$ entries of $x+1$ and $k_1 - c_{x+1}$ entries of $x$. $k_2$ will then decrease $k_2$ entries of $x$, since $c_{x+1} \ge k_2$.↵
↵
- first $k_2$ then $k_1$ — $k_2$ will decrease $k_2$ entries of $x+1$. $k_1$ will decrease $c_{x+1} - k_2$ entries of $x+1$ and $k_1 + k_2 - c_{x+1} < c_x + k_2$ entries of $x$. The inequality shows that $k_1$ will only decrease entries of $x$ and $x+1$.↵
↵
2. $k_2 > c_{x+1}$. This case is tedious as there are subcases with $x - 1$, but the logic is the same, so I leave it as an exercise to the reader :)↵
↵
Therefore, in all cases both orders of operations result in the same array, so we can swap adjacent operations without any effect. And if we can swap adjacent operations, we can get any permutation of operations we want.↵
↵
</spoiler>↵
↵
---↵
↵
Tasks for practice↵
------------------↵
↵
[Problem from AtCoder ABC](https://atcoder.jp/contests/abc424/tasks/abc424_g)↵
↵
[Problem from JOISC 2023](https://qoj.ac/contest/1210/problem/6339)↵
↵
---↵
↵
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$↵
↵
<spoiler summary="Proof">↵
Consider 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 > 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)$.↵
</spoiler>↵
↵
Another example is [problem:1774B]. 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.↵
↵
<spoiler summary="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.↵
↵
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 (there are more allowed colors we can put than the number of banned colors).↵
</spoiler>↵
↵
Here is a problem where you can try applying the idea yourself [problem:1893D]↵
↵
---↵
↵
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$?↵
↵
<spoiler summary="Solution">↵
↵
We 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 > 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$.↵
↵
1. $k = 1$. $m \ge a_1$↵
↵
2. $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)$.↵
↵
</spoiler>↵
↵
Right now I can only remember this problem [problem:2181G], 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](https://www.facebook.com/codingcompetitions/hacker-cup/2025/round-2/problems/B)↵
↵
---↵
↵
Lastly, there is problem D2 from Open Olympiad 24-25 day 2 [contest:2080], which motivated me to understand this theorem. The fact below is crucial for the solution, so it's under a spoiler as well.↵
↵
<spoiler summary="Fact">↵
↵
1. The greedy algorithm to always decrease maximums produces the lexicographically largest possible sorted array among all arrays which are achievable with the operations.↵
↵
<spoiler summary="Proof">↵
Without loss of generality array $a$ is sorted in non-decreasing order and operations decrease maximums in such a way that the array remains sorted.↵
↵
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 < a_j$ (which also means that $i < 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 < 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 if we fix the order of operations, then the operations which pick maximums produce an array with maximal prefix sums. In that case the order of operations doesn't matter, so we'll always get the same array no matter what initial order we've chosen.↵
</spoiler>↵
↵
</spoiler>↵
↵
