Observations

Given an array \(A = (1, 2, 3)\), what is the \(ans\) (answers) after performing \(K\) operations? (We also demonstrate \(A\) that achieves \(ans\), but note that this is just an example.)

• For \(K = 1\), \(ans = 2\) for \(A = (2, 2, 3)\)
• For \(K = 2\), \(ans = 2\) for \(A = (3, 2, 3)\)
• For \(K = 3\), \(ans = 3\) for \(A = (3, 4, 3)\)
• For \(K = 4\), \(ans = 3\) for \(A = (4, 4, 3)\)
• For \(K = 5\), \(ans = 4\) for \(A = (4, 4, 6)\)

We see that \(ans\) is monotonically increasing with respect to \(K\). We sometimes refer to this property as “solutions are monotonic.”

Binary search over solutions

When “solutions are monotonic,” binary search over solutions is often effective. This is a technique that, instead of directly finding \(ans\), determines the solution by binary searching by questions: “is it possible to make \(ans\) greater than or equal to \(X\)?”

This stems from the fact that it is often easier to solve decision problems in the form of “is it possible to make \(ans\) greater than or equal to \(X\)?” (than solving the original problem directly.)

Solving the decision problem

What we need to solve in our problem is:

“Is it possible to make \(ans\) greater than or equal to \(X\) (with \(K\) operations)?”

Or equivalently,

“Is ‘the number of operations required to make \(ans\) greater than or equal to \(X\)’ less than or equal to \(K\)?”

or

“Is ‘the number of operations required to make all elements at least \(X\)’ less than or equal to \(K\)?”

The last problem can be solved easily. The minimum number of operations required is the sum of

• \(0\), if \(A_i \ge X\); or
• \(\displaystyle \Big\lceil \frac{X - A_i}{i} \Big\rceil\), if \(A_i\lt X\);

over all \(i\). It suffices to determine if the sum is \(K\) or less.

Solution

In our problem, the answer is always \(1\) or greater. Also, the answer is strictly less than \(A_1 + K + 1\) (because this value cannot be reached by spending all \(K\) operations for \(A_1\)). Thus, the bounds of the binary search can be set to this range.

The decision problem above can be solved in \(O(N)\) time. Since it suffices to solve it \(O( \log (A_1 + K))\) times, the time complexity is \(O(N \log(A_1 + K))\).

Sample code

n, k = map(int, input().split())
a = [0] + list(map(int, input().split())) # Convert to 0-based indexing

def isok(x):
    # Is it possible to make `ans` greater than or equal to x?
    nk = 0
    for i in range(1, n + 1):
        if a[i] < x:
            nk += (x - a[i] + i - 1) // i # ceil((x - a[i]) / i)
            if nk > k:
                return False
    return True

ok = 1
ng = a[1] + k + 1

while ng - ok > 1:
    m = (ok + ng) // 2
    if isok(m):
        ok = m
    else:
        ng = m

print(ok)

Notes

• If you try to use decimals to compute ceil, precision errors may cause WA (wrong answer). As a rule of thumb, try to stick to integers as much as possible.

• Also, beware of overflows. Depending on implementation, ng may overflow. Also, overflows of nk in the decision problem are hard to notice.