Official Analysis (C++)

Explanation

We iterate through all elements and binary search on the largest we can make them.

Say we want to increase $a_i$ to $x$. To do so, we need the following:

• $a_{i+1}$ to be at least $x-1$
• $a_{i+2}$ to be at least $x-2$
• and so on and so forth...

Try it yourself with some toy examples to see why this is true.

There's two possible outcomes for how this might end.

1. Either we hit a point where $a_{i+n}$ is already at least $x-n$. At this point, we can stop searching and calculate the total number of operations.
2. We hit the final element and it turns out that we need it to be something greater than its current value, which is impossible.

As long as the second scenario never happens and the total number of operations is less than the max we were given, everything's fine.

Implementation

Time Complexity: $\mathcal{O}(n^2 \log k)$

Copy
#include <algorithm>
#include <cstdint>
#include <iostream>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

int main() {

Copy
import java.io.*;
import java.util.*;

public class ToBecomeMax {
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
		int testNum = Integer.parseInt(read.readLine());
		for (int t = 0; t < testNum; t++) {
			StringTokenizer initial = new StringTokenizer(read.readLine());
			int len = Integer.parseInt(initial.nextToken());

Copy
for _ in range(int(input())):
	len_, max_ops = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]

	best = -float("inf")
	for start in range(len_):
		lo = arr[start]
		hi = arr[start] + max_ops
		doable = -1
		while lo <= hi: