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:
For an array A, f(A) is defined to be the maximum score that can be attained by repeating this process:
- Choose two adjacent elements. Add the smaller one to your score, and delete the larger one.
Given an array A, you are to process Q point updates to it.
Each update replaces a single element.
After each replacement, compute f(A).
EXPLANATION:
Our first order of business is figuring out how to compute f(A) at all.
To do that, let’s consider the array B of length N-1, where B_i = \min(A_i, A_{i+1}).
Each operation then involves choosing some index i, adding B_i to the score, and deleting \max(A_i, A_{i+1}) from A.
Let’s analyze how this deletion changes B when done on index i.
Suppose A_i \geq A_{i+1}, so that performing the operation deletes A_i.
Then, note that the only “new” pair of adjacent elements are A_{i-1} and A_{i+1}: every other adjacent pair remains as it was in A.
This means:
- B_{i-1} used to be \min(A_{i-1}, A_i), but it’s now \min(A_{i-1}, A_{i+1}).
- Every other value in B remains exactly the same; just that B_i is no longer present and so everything to the right of i has shifted one position left.
So, functionally we just deleted B_i from the array B, and modified the value B_{i-1}.
Since A_i \geq A_{i+1}, we definitely have \min(A_{i-1}, A_i)\geq\min(A_{i-1}, A_{i+1}), i.e. the new value is smaller or equal to the old value.
That is, our operation did two things:
- Deleted B_i from B and added it to our score.
- Either reduced B_{i-1} or kept it unchanged; it certainly didn’t increase it.
This was assuming A_i \geq A_{i+1}; if it’s the opposite then the result is basically the same: B_{i+1} gets reduced (or remains the same), and then B_i is deleted.
Either way, the operation deletes one element and makes another one smaller (or leaves it unchanged).
Looking at how the array B changes, we immediately obtain an upper bound on the answer:
B_1 + B_2 + \ldots + B_{N-1}.
This is because we’re adding elements of B to the score and maybe reducing them during the process; so of course the best case scenario is when there are no reductions at all.
It’s not hard to see that this upper bound is indeed attainable.
A simple construction is to repeatedly take the maximum element in A, and then perform the operation with it and its largest neighbor – it’s easy to see that doing this will not reduce any element of B, so we’ll obtain B_1 + B_2 + \ldots + B_{N-1} as our score in the end.
(This greedy idea is perhaps something you thought of initially, this also serves as a proof of why it works - and more importantly, gives a simple way of knowing what the final value is without having to actually perform the simulation).
Since B_i = \min(A_i, A_{i+1}), we really just have
Once we have this simple characterization of f(A), handling point updates is trivial: each point update changes only two adjacent minimums, so just subtract out the old ones and add in the new ones.
TIME COMPLEXITY:
\mathcal{O}(N + Q) per testcase.
CODE:
Editorialist's code (PyPy3)
for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
ans = sum(min(a[i], a[i+1]) for i in range(n-1))
while q > 0:
q -= 1
i, x = map(int, input().split())
i -= 1
if i > 0:
ans -= min(a[i], a[i-1])
ans += min(a[i-1], x)
if i+1 < n:
ans -= min(a[i], a[i+1])
ans += min(a[i+1], x)
a[i] = x
print(ans)