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.

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 \gt k_2$$$. I denote $$$k_1$$$ as the first operation and $$$k_2$$$ as the second.

Assume the array $$$a$$$ is sorted and the operations decrease such positions that the array remains sorted (we can do so by selecting first by greater value then by smaller position, this operation does indeed keep the array sorted).

Let's start with a simple case where the first operations only decreases the maximum value $$$x$$$. Denote $$$c_x$$$ as the frequency of $$$x$$$ in the array $$$a$$$. 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 x$$$, then:

• If we do first $$$k_1$$$ then $$$k_2$$$, then after the first operation there will be $$$c_x - k_1$$$ occurences of $$$x$$$ left and at least $$$k_1$$$ occurences of $$$x - 1$$$. $$$k_2$$$ will decrease all remaining $$$x$$$ (since $$$k_1 + k_2 \ge c_x$$$) and $$$k_1 + k_2 - c_x$$$ positions with $$$x - 1$$$ (and no other value since $$$k_1 + k_2 - c_x \le k_2 \le k_1$$$).

• If we do first $$$k_2$$$ then $$$k_1$$$, then $$$k_1$$$ will decrease $$$c_x - k_2$$$ positions with $$$x$$$ and $$$k_1 + k_2 - c_x$$$ positions with $$$x - 1$$$.

Now consider the more general case where $$$x$$$ is the maximum number such that $$$c_x + c_{x+1} + \ldots \gt 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 operation would look like this

Red stripes show the positions that are decreased in the first operation. We can split the first operation in three parts — $$$x$$$, $$$x+1$$$ and $$$ \gt x+1$$$, and the number of positions that are decreased in each part is $$$L$$$, $$$c_{x+1}$$$ and $$$R$$$ respectfully.

Assume $$$k_2 \le R$$$. Then if we swap the operations, the positions which are decreased in each operation won't change. That is because all elements in $$$R$$$ share the same relative differences and the number before is strictly less and won't be considered.

Now, as $$$k_2 \gt R$$$, all elements in that part will just be decreased twice, hence we can ignore them. Let's look at what happens when $$$k_2$$$ only decreases $$$x + 1$$$.

Here for the top array blue means the positions which will be decreased if $$$k_2$$$ was the first operation, red means the positions which would be decreased by $$$k_1$$$ regardless whether it's the first or the second operation and green color shows the new elements which are decreased if $$$k_1$$$ is the second operation. As we can see the window of size $$$c_x - L$$$ remains, and green stripes are in the same place as blue stripes at the bottom. Basically what happens is, instead of decreasing some $$$x+1$$$ $$$k_1$$$ decreases some extra $$$x$$$, which are also decreased by $$$k_2$$$ if it's the second operation.

Now assume $$$k_2$$$ decreases all $$$x+1$$$. Let's look at what new value will $$$k_1$$$ decrease as the second operation and $$$k_2$$$ as the first, if we increment $$$k_2$$$. For the first $$$c_x - L$$$ incrementations both $$$k_1$$$ and $$$k_2$$$ decrease an $$$x$$$, then they both decrease $$$x-1$$$.

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, we can get any permutation of operations.

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 \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 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.

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 \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$$$.

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)$$$.

1. 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.