# MINOPS1 - Editorial

Author: raysh07
Tester: tabr
Editorialist: iceknight1093

Simple

None

# PROBLEM:

For an array B, define f(B, K) to be the minimum number of operations required to make the sum of adjacent differences be \leq K.
In one operation, you can choose a maximal segment of B that contains the same element, and either add 1 or subtract 1 from them all.

You’re given an array A. Answer Q queries on it:

• Given L, R, K, find f(A[L\dots R], K)

# EXPLANATION:

Let’s try to find just f(B, K) for a fixed array B and value K.
Let S = \sum_{i=2}^M |B_i - B_{i-1}|. We want to make S \leq K.

When we operate on subarray [L, R], note that adjacent differences don’t actually change that much.
In particular, the only adjacent differences that change are:

• |B_L - B_{L-1}|, if L \gt 1.
• |B_R - B_{R+1}|, if R \lt M.

Everything else remains the same.
Further, the differences that do change, change by either +1 or -1.
So, a single operation can change S by some integer between -2 and +2.

Our aim is to make S \leq K, so ideally every move we make changes S by -2; and if we can’t manage that, -1.

In the easy version, the constraints are small enough that you can simply bruteforce this.
That is, while S \gt K, try every possible maximal subarray and see if operating on it can reduce S by 2.
If you find such a subarray, great. Otherwise, S can always be reduced by 1 by operating on the prefix of equal elements.

This is fast because of the fact that 1 \leq A_i \leq 30.
So, within at most 15\cdot N moves, we’re guaranteed that all the elements of A will become equal (and hence S = 0 which is the best we can do) - just by making all the elements equal to 15.
Each move is simulated in \mathcal{O}(N) time since we just find all maximal segments of which there are at most N.

This means each query is answered in \mathcal{O}(15\cdot N^2) time, or more precisely, \mathcal{O}(\max(A)\cdot N^2) time.
Doing this for each query multiplies the complexity by Q, which is still fine.

Since N, Q, A_i \leq 30, the number of operations is bounded by approximately
30\cdot 30\cdot 30\cdot 15 \approx 4\cdot 10^5 per testcase.
With only 10 test cases, this is fine.

# TIME COMPLEXITY:

\mathcal{O}(N^2 \cdot\max(A)\cdot Q) per testcase.

# CODE:

Editorialist's code (Python)
def compress(b):
ret = []
for x in b:
if len(ret) == 0 or ret[-1] != x: ret.append(x)
return ret

def solve(b, k):
ops = 0
while True:
b = compress(b)
n = len(b)
sm = sum([abs(b[i] - b[i-1]) for i in range(1, n)])
if sm <= k: break

ops += 1
for i in range(1, n-1):
if b[i] < min(b[i-1], b[i+1]):
b[i] += 1
break
elif b[i] > max(b[i-1], b[i+1]):
b[i] -= 1
break
else:
if b[0] <= b[-1]: b[0] += 1
else: b[0] -= 1
print(ops)

for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
for j in range(q):
l, r, k = map(int, input().split())
solve(a[l-1:r], k)


I did the exact same thing and the complexity for me was approximately OK as well but the fact that i got TLE in a easy version where all constraints are <= 30 still gives me a wrinkle in my stomach , can someone just go through my code and tell me why i get a TLE
Procedure is the same , just check if u can reduce it by 2 , if not then reduce it by 1 although it sounds simple , implementing it required some typing skills as the code turned out to be longer than what i would’ve wanted.
Here’s the link to the submission :
https://www.codechef.com/viewsolution/1086752589