PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: raysh07
Editorialist: iceknight1093
DIFFICULTY:
Cakewalk
PREREQUISITES:
Binary search
PROBLEM:
A smoothen operation on an array A is defined as follows:
- Choose x
- Let S = 0
- For i = 1, 2, \ldots, N in order:
- If A_i \ge x, set A_i = x and add A_i - x to S.
- If A_i \lt x, add \min(S, x - A_i) to A_i and subtract the same amount from S.
Given an array, you can smoothen at most one of its subarrays.
Is it possible to sort the array in non-decreasing order?
If yes, find the maximum X that can achieve this.
EXPLANATION:
If the array is already sorted, then any X is valid (we can always choose the first element as the subarray; and it either remains the same or decreases so the array will remain sorted.)
So, in this case no finite maximum exists.
On the other hand, observe that for any X \ge \max(A), the array will not change at all no matter what we do.
Also choosing X = 1 and operating on the whole array will turn it into [1, 1, \ldots, 1] which is sorted; so clearly a finite maximum exists.
Suppose we fix a value of X.
How do we tell if a valid subarray exists?
To answer that, suppose we choose to smooth subarray [L, R], and the array is sorted afterwards.
Observe that as the result of smoothing [L, R], all elements in the range [L, R] will become \le X.
Assuming that the array is sorted, let’s look at element A_{L-1} (assuming L \gt 1.)
If A_{L-1} \gt X, then smoothing [L, R] can’t possibly sort A, because A_L will become \le X and hence smaller than A_{L-1}.
Thus, we must have A_{L-1} \le X.
However, with A_{L-1} \le X, note that we could also just operate on the subarray [L-1, R] instead - the smoothing operation isn’t going to change A_{L-1} since it’s the first element and so there’s no “excess” to give it; thus the resulting array will be the same as if we operated on [L, R].
Similarly, let’s look at A_{R+1}.
If A_{R+1} \ge X, then operating on [L, R+1] will always reduce A_{R+1} to X; which will still leave the array sorted because A_R \le X must hold after smoothing [L, R].
If A_{R+1} \lt X, then A_{R} must also be \lt X for the array to be sorted - which means all of A_L, \ldots, A_{R-1} are also \lt X (since if any of them are initially \ge X then smoothing would reduce them to X, breaking sortedness since A_R is smaller.)
But if all these elements are \lt X then smoothing with respect to X does nothing to the subarray anyway, which means the original array is already sorted.
We’re dealing with the case of only not-sorted arrays now, so we don’t need to worry about this case.
Either way, observe that if operating on [L, R] is possible, then [L-1, R] and [L, R+1] are also both valid subarrays to operate on.
Repeatedly using this fact, we see that it’s enough to just operate on [1, N], i.e. the entire array!
Thus, checking if a single X can smooth the array is simple: just simulate the procedure on the whole array!
To find the maximum valid X, we can use binary search.
This is because, if operating with some X on [1, N] results in a sorted array, then operating using X-1 will also result in it being sorted.
Proof
Note that smoothing by X and ending up with a sorted array will essentially take the leftmost element that’s \gt X and then set the entire suffix starting from here to X; and in particular the prefix up to that point must itself be sorted.
When smoothing by X-1 we’ll do almost the same thing.
Specifically,
- If the sorted prefix upto the first element \gt X doesn’t contain a copy of X itself, then we’ll just end up setting the same suffix as before to all X-1, which results in a sorted array (since the prefix beforehand has values only \lt X and is already sorted.)
- If X does appear, then these copies of X will additionally be set to X-1, but again the whole remaining suffix will become X-1 so the array will be sorted.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if a == sorted(a):
print(-1)
continue
lo, hi = 1, max(a)
while lo < hi:
mid = (lo + hi + 1)//2
b = a[:]
s = 0
for i in range(n):
if b[i] >= mid:
s += b[i] - mid
b[i] = mid
else:
add = min(s, mid - b[i])
b[i] += add
s -= add
if b == sorted(b): lo = mid
else: hi = mid-1
print(lo)