Editorial

First, it is necessary to consider the case when $k=0$. In this case, we cannot decrease any number, so if there is at least one number $a_i>0$, the answer is $-1$. Otherwise, all numbers are already non-positive, so we can perform $0$ operations.

Now let's consider the solution for each test group for $k>0$:

Block 1

In the first group, the value of $t=0$, so for one operation, we can simply decrease any number $a_i$ by $k$. To make the value $a_i$ non-positive, it is necessary to perform with it at least $\lceil \frac{max(0,a_i)}{k}\rceil$ operations. Therefore, the minimum number of operations needed to make all numbers non-positive is $\sum _{i=1}^n\lceil \frac{max(0,a_i)}{k}\rceil$.

Solution: [link to the solution]

Block 2

To solve this group, it was necessary to determine the criterion for making all numbers non-positive exactly in $x$ operations. For this, let's try to reduce the problem to the case of $t=0$. Specifically, let's say that for one operation, we increase all $n$ numbers by $t$, and decrease one number $a_i$ by $(k+t)$. It can be seen that this operation is equivalent to the operation from the condition. With this definition, we can say that after performing $x$ operations, all $a_i$ will increase by $xt$. After this, to make the number $(a_i+xt)$ non-positive, it is necessary to perform with it at least $\lceil \frac{max(0,a_i+xt)}{k+t}\rceil$ operations. Therefore, we get a simple criterion: all numbers can be made non-positive in exactly $x$ operations if and only if $\sum _{i=1}^n\lceil \frac{max(0,a_i+xt)}{k+t}\rceil \le x$.

It may seem that a simple binary search for the answer can be used. But such a solution is incorrect, as there is not always an answer that uses exactly $(x+1)$ operations, even if there is an answer that uses exactly $x$ operations. For example, on the test with $n=2,k=100,t=99,a_1=1,a_2=1$, all numbers can be made non-positive in $2$ operations, but not in $3$.

It can be proven that when the answer exists, it does not exceed $nm$, where $m=\max (0,\underset{i=1}{\overset{n}{\max }}{a}_i)$. Therefore, it is possible to check all possible answer options from 0 to $nm$, using the described criterion. To check the criterion, it is necessary to perform $n$ operations, so the total complexity of this solution is $O(n^{2}m)$.

Solution: [link to the solution]

Block 3

We will maintain the current answer $x$, which initially equals zero, as well as the array $cnt$, where $cn{t}_i$ denotes the number of operations performed on position $i$. On the next iteration of the algorithm, we will iterate through all positions $i=1\dots n$. If the inequality $\lceil \frac{max(0,a_i+xt)}{k+t}\rceil >cn{t}_i$ is satisfied, it is necessary to increase $cn{t}_i$ and $x$ by $(\lceil \frac{max(0,a_i+xt)}{k+t}\rceil -cn{t}_i)$. If the value of $x$ does not increase on the current iteration of the algorithm, the answer has been found. If $x$ becomes greater than $nm$, it is necessary to output $-1$. It can be proven that this solution works in $O(nm)$ time. It can also be noted that this solution will perform exactly one iteration on the tests of the first group and will work in $O(n)$ time.

Solution: [link to the solution]

Block 4

First, let's understand how the constraint $1\le a_i$ helps. Firstly, the criterion check described in the second point is slightly simplified: $\sum _{i=1}^n\lceil \frac{a_i+xt}{k+t}\rceil \le x$. Secondly, it can be noted that when all $a_i\ge 1$, each position $i$ will need to perform at least one operation. This means that if $k\le (n-1)t$, the answer is $-1$. Indeed, suppose that there is an optimal answer. Since each position has been operated at least once, it is possible to reduce the number of operations at each position by $1$. The answer will remain valid, as each $a_i$ will not increase. Therefore, we have obtained a solution with fewer operations, which contradicts the assumption of the optimality of the answer.

Now let's consider the case when $k>(n-1)t$. Suppose that exactly $x$ operations can make all numbers non-positive. Then it can be seen that exactly $(x+n)$ operations can also make all numbers non-positive. Indeed, it is possible to simply perform one more operation at each position $i$, after which the values at all positions will decrease by $(k-(n-1)t)$. Therefore, it is possible to iterate through the remainder when dividing by $n$, and perform a binary search on numbers $x$ with such a remainder. The complexity of this solution is $O(n^2\log ans)$.

Solution: [link to the solution]

Block 5

Unlike the previous solution, we will iterate through the remainders $rem$ ($0\le rem<n$) from the answer when dividing by $n$ in a random order. We will also maintain the minimum found answer $x$ among all the remainders considered previously. Then, before starting the binary search on the current remainder, we will check if the answer is improved. To do this, it is necessary to check the previously described criterion for the maximum number less than $x$ with a remainder of $rem$. Only if the criterion is satisfied, the binary search needs to be started. It can be proven that in this solution, the binary search will be started $O(\log n)$ times, and therefore the total complexity is $O(n^2+n\log n\log ans)$.

Solution: [link to the solution]

Block 6

To speed up the previous solution, it is sufficient to use the idea described in point 5. The complexity of this solution is $O(n\log n\log ans)$.

Solution: [link to the solution]

Block 7

To speed up the previous solution, it is sufficient to use the idea described in point 5. The complexity of this solution is $O(n\log n+{\log }^{2}n\log ans)$.

Solution: [link to the solution]

Block 8

For convenience, let's assume that all numbers $a_i$ are sorted in descending order. In the last four blocks, the numbers $a_i$ could be negative, but in reality, this does not complicate the problem very much. Indeed, let's denote by $n^{\prime }$ the maximum number not greater than $n$ such that $k>(n^{\prime }-1)t$. Then it can be seen that at least one operation could have been performed with at most $n^{\prime }$ positions (a proof similar to the one from point 4 can be given). This means that for the last $(n-n^{\prime })$ positions, no operations were performed at all.

Then for the first $n^{\prime }$ numbers, the problem can be solved in the same way as in group 4, and then it is necessary to check that the last $(n-n^{\prime })$ numbers remain non-positive after performing the found number of operations.

Solution: [link to the solution]

Block 9

To speed up the previous solution, it is sufficient to use the idea described in point 5. The complexity of this solution is $O(n^2+n\log n\log ans)$.

Solution: [link to the solution]

Block 10

To speed up the quadratic solution, it is necessary to learn how to quickly check the criterion described in point 2. The difference from the solution of the sixth group is that $a_i$ can be less than zero, and therefore some $a_i$ should not add negative values $\lceil \frac{a_i+xt}{k+t}\rceil$ to the sum.

Since all values of $a_i$ are sorted in descending order, it is possible to first find the maximum position $i$ such that $a_i+xt\ge 0$. For all subsequent positions, the contribution to the desired sum will be zero, so these positions can be simply forgotten. For the found prefix of positions $1\dots i$, the idea from point 6 can be used, but it is necessary to learn how to quickly calculate the number of numbers greater than a given one in the prefix. This can be done using the technique of "partial cascading". This technique allows you to respond to necessary requests in the same time $O(\log n)$ and requires $O(n\log n)$ time and memory for construction. With its help, the problem can be solved in time $O(n\log n+n\log n\log ans)$.

Solution: [link to the solution]

Block 11

To speed up the previous solution, it is sufficient to use the idea described in point 5. The complexity of this solution is $O(n\log n+{\log }^{2}n\log ans)$.

Solution: [link to the solution]

It is also worth noting that there is another, simpler, solution that was found during the testing of the problem by Yevhen Sobolev. The main idea is that a simple binary search for the answer can be used, but to check that the answer is valid, it is necessary to check not at the point $mid$, but in the window of size $n$ on the interval $[mid;mid+n)$. To quickly check the criterion described in point 2, it is possible to first find the value of the sum at $x=mid$ in $O(n)$ time. To recalculate the value of the sum when increasing $x$ by 1, it can be noted that each term of the sum can increase at most once by $1$. Indeed, when increasing $x$ by 1, the numerator of the fraction increases by $t$, and the denominator equals $(k+t)$. Since the inequality $k>(n-1)t$ holds, then $k+t>(n-1)t+t=nt$. Therefore, when increasing by $t$, the value of the fraction can increase at most $1$ for only $n$ times, so the value of the fraction can increase at most by $1$. The time at which this value will increase can be found using the formula, and at the appropriate time, the current value of the sum should be increased by $1$. Therefore, it is possible to solve the problem in time $O(n\log ans)$.

Solution: [link to the solution]

Notes and Interesting Facts:

• When implementing the solution, it is necessary to be very careful with multiplication operations to avoid accidentally exceeding the limits of the 64-bit data type. The most dangerous place where the 64-bit type can overflow is the multiplication of $x$ by $t$ in the check function (for example, if setting the limits of the binary search to $10^{15}$). However, it can be noted that since $k>(n-1)t$, then $nt\le 2k=2\cdot 10^9$. Since the answer does not exceed $nm$ ($x\le nm$), then $xt\le ntm\le 2\cdot 10^9\cdot 10^9=2\cdot 10^{18}$. This means that the right limit of the binary search can be set to the value $\frac{2\cdot 10^{18}}{t}$, and there is no need to worry about overflow anymore.

• This problem was initially proposed for position "A" with an incorrect editorial solution described in point 2 (a simple binary search for the answer). After finding the correct solution, the complexity of the problem sharply increased, and the problem was moved to the last position.