PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: iceknight1093
Tester: sushil2006
Editorialist: iceknight1093
DIFFICULTY:
Simple
PREREQUISITES:
None
PROBLEM:
You’re given an array A with pairwise distinct elements.
You can do the following:
- Choose i such that A_i \lt \min(A_{i-1}, A_{i+1}), and set A_{i-1} and A_{i+1} both to A_i.
Find the minimum possible value of \text{sum}(A) after finitely many operations.
EXPLANATION:
Let’s call index i a valley if A_i \lt \min(A_{i-1}, A_{i+1}).
Observe that if index i is not a valley initially, then it can never be made a valley using the given operation.
This is because our operation can only reduce elements (not increase them), and so:
- Reducing a value at a neighboring index is not going to help make index i a valley, to the contrary it makes it “more difficult” for it to become a valley at all.
- Reducing the value of A_i itself is only possible when it’s adjacent to a valley; but then after the operation it will be equal to the valley used to reduce it (in particular, it won’t be strictly smaller.)
Thus, the only valleys possible at all are the ones that are valleys in the original array.
Further, note that after operating on a valley, it will no longer be a valley; and so can’t become a valley in the future either.
And one final observation is that two valleys cannot be adjacent to each other, since the larger element among them can’t satisfy the valley condition then.
We hence know that:
- Valleys are non-adjacent
- No new valleys can be created
- Each existing valley can be operated on at most once.
We use these observations to solve the problem.
Our goal is to minimize \text{sum}(A).
Let’s look at an index i.
There are three possibilities:
- Index i is not adjacent to a valley.
In this case, the value A_i cannot be changed at all. - Index i is adjacent to exactly one valley, i.e. either i-1 or i+1 is a valley (but not both.)
In this case, by operating on the adjacent value we’re able to reduce the value of A_i to that of the neighboring valley. - Index i is adjacent to two valleys.
In this case, the best we can do is reduce A_i to the lower of the values of its neighbors.
So, for each index we know the best possible value it can attain.
The question now is: can we make every index attain its best possible value, simultaneously?
It’s not obvious that this is possible, because performing an operation might end up turning other valleys into non-valleys - for instance the array [2, 1, 2, 1, 2] has valleys at indices 2 and 4, but it’s not possible to operate on both of them since operating on one makes the other not be a valley.
Luckily for us, there’s an additional constraint on the input: all the values in the original array are pairwise distinct.
This constraint ensures that we are, in fact, able to operate on every valley and turn every element into its optimal final value.
The construction is simple: simply operate on valleys in descending order of their value. Because no two elements are equal, it can be shown that doing this won’t create any issues with accidentally un-valleying a valley.
Thus, the solution is as follows:
- Find the optimal final value for each index, which is:
- The initial value itself, if it’s not adjacent to a valley; or
- The minimum value of a neighbor valley otherwise.
- The answer is then simply the sum of all optimal values.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n = int(input())
a = [0] + list(map(int, input().split())) + [0]
valley = [0]*(n+2)
for i in range(1, n+1):
if a[i] < min(a[i-1], a[i+1]):
valley[i] = 1
ans = 0
for i in range(1, n+1):
x = a[i]
if valley[i-1]: x = min(x, a[i-1])
if valley[i+1]: x = min(x, a[i+1])
ans += x
print(ans)