PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
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)