To Become Max (Codeforces 1856C)
Tags: DP, binary search

You are given an array of integers $$$a$$$ of length $$$n$$$.In one operation you:   Choose an index $$$i$$$ such that $$$1 \le i \le n - 1$$$ and $$$a_i \le a_{i + 1}$$$.  Increase $$$a_i$$$ by $$$1$$$. Find the maximum possible value of $$$\max(a_1, a_2, \ldots a_n)$$$ that you can get after performing this operation at most $$$k$$$ times.

Input: Each test contains multiple test cases. The first line of input contains a single integer $$$t$$$ ($$$1 \le t \le 100$$$) — the number of test cases. The description of the test cases follows.The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 1000$$$, $$$1 \le k \le 10^{8}$$$) — the length of the array $$$a$$$ and the maximum number of operations that can be performed.The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \le a_i \le 10^{8}$$$) — the elements of the array $$$a$$$.It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$1000$$$.

Output: For each test case output a single integer — the maximum possible maximum of the array after performing at most $$$k$$$ operations.

Note: In the first test case, one possible optimal sequence of operations is: $$$[\color{red}{1}, 3, 3] \rightarrow [2, \color{red}{3}, 3] \rightarrow [\color{red}{2}, 4, 3] \rightarrow [\color{red}{3}, 4, 3] \rightarrow [4, 4, 3]$$$.In the second test case, one possible optimal sequence of operations is: $$$[1, \color{red}{3}, 4, 5, 1] \rightarrow [1, \color{red}{4}, 4, 5, 1] \rightarrow [1, 5, \color{red}{4}, 5, 1] \rightarrow [1, 5, \color{red}{5}, 5, 1] \rightarrow [1, \color{red}{5}, 6, 5, 1] \rightarrow [1, \color{red}{6}, 6, 5, 1] \rightarrow [1, 7, 6, 5, 1]$$$.

Sample Inputs:
6
3 4
1 3 3
5 6
1 3 4 5 1
4 13
1 1 3 179
5 3
4 3 2 2 2
5 6
6 5 4 1 5
2 17
3 5

Sample Outputs:
4
7
179
5
7
6

Solution (Python):
DEBUG = False
t = int(input())
for _ in range(t):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    global_max = max(a)
    for i in range(n - 1):
        current = a[i]
        distance = 1
        operations = k
        DEBUG and print(f'current = a[{i}] which is {a[i]}')
        for j in range(i + 1, n):
            if a[j] == current - 1:
                distance += 1
                current = a[j]
                DEBUG and print(f'moving. current = {current}, distance = {distance}')
            elif a[j] < current - 1:
                if operations <= current - 1 - a[j]:
                    DEBUG and print('unable to compensate')
                    break
                else:
                    operations -= current - 1 - a[j]
                    DEBUG and print(f'current is {current}, compensating a[j]={a[j]} by {current - 1 - a[j]}')
                    DEBUG and print('operations is now', operations)
                    distance += 1
                    current -= 1
            elif a[j] > current - 1:
                if operations // distance >= a[j] - current + 1:
                    operations -= (a[j] - current + 1) * distance
                    current = a[j]
                    distance += 1
                    DEBUG and print(f'raising up current to {a[j]}. distance is {distance}. score is {current + distance - 1}')
                else:
                    current += operations // distance
                    DEBUG and print(f'raising current as much as possible to {current}, distance is {distance}')
                    break
        local_max = current + distance - 1
        DEBUG and print('local max', local_max)
        DEBUG and print('-------end of current i iteration--------')
        global_max = max(global_max, local_max)
    print(global_max)

Solution (Python):
def f(new, j):
    global mas
    global n
    global k
    summ = 0
    mas_2 = mas.copy()
    while j < n and new > mas_2[j] and (summ + new - mas_2[j] <= k):
        summ += new - mas_2[j]
        j += 1
        new -= 1
    if j < n and new <= mas_2[j]:
        return True
    return False
t = int(input())
mas_ans = []
for q in range(t):
    (n, k) = map(int, input().split())
    mas = [int(el) for el in input().split()]
    ans = max(mas)
    for i in range(n):
        while f(ans + 1, i):
            ans += 1
    mas_ans.append(ans)
for i in range(t):
    print(mas_ans[i])

Solution (Python):
res = []
for i in range(int(input())):
    (n, k) = map(int, input().split())
    a = list(map(int, input().split()))
    val = max(a)

    def func(m, idx):
        oper = 0
        while idx < n and m > a[idx] and (oper + m - a[idx] <= k):
            oper += m - a[idx]
            m -= 1
            idx += 1
        if idx < n and m <= a[idx]:
            return True
        return False
    for i in range(n):
        while func(val + 1, i):
            val += 1
    res.append(val)
for val in res:
    print(val)