PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: etherinmatic
Tester: kaori1
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting, sets/priority queues
PROBLEM:
You are given an array of length N, where N is odd. You can do the following:
- Choose three distinct indices i, j, k.
- Delete A_i, A_j, A_k from the array.
- Insert A_i + A_j - A_k into the array.
In the end, a single element will remain. Your aim is to maximize this final value.
Answer Q queries, each asking for the answer when a prefix of A is considered.
EXPLANATION:
Letās first solve for a single array A, forgetting multiple queries.
No matter how the operations are performed, the final value is going to be a combination of the initial A_i values - just that each of them will either have a +1 or -1 coefficient (i.e, be added or subtracted).
The ideal situation is, of course, when every positive number receives a +1 coefficient and every negative number receives -1.
However, that isnāt always possible.
For example, analyzing some small cases:
- For N = 3, we have three values (say a, b, c).
The operation lets us end up with the sum of two of them, minus the third. - For N = 5, we have five values (say a, b, c, d, e).
Letās say that initially, everything has the + sign.
After the first operation, four values will have the + sign and one will have -.
After the second operation,- If the newly combined element is one of the added ones, weāll have three plus signs and two minuses.
- If the newly combined element is subtracted, weāll still have three plus signs and two minuses.
- In particular, you may observe that for N = 5, itās possible to obtain any combination of 3 pluses and two minuses.
The last part seems suspicious: and indeed, we can generalize it.
Claim: For a given odd N, no matter how the operations are performed, the final element will be the sum of \frac{N+1}{2} of the elements, minus the sum of the other \frac{N-1}{2} elements.
Further, any set of elements can be chosen as the ones being added.
Proof
There are two things to be proved here: first that the final element will be the sum of \frac{N+1}{2} of the elements, minus the sum of the other \frac{N-1}{2} elements, and second that any such configuration is achievable.
The first claim can be proved using induction.
For N = 1 itās trivially true.
For N\gt 1, perform any move initially; leaving you with one ācombinedā element thatās two pluses and one minus.
Now, by the inductive hypothesis, performing moves on the remaining array of size N-2 will leave us with something thatās \frac{N-1}{2} pluses and \frac{N-3}{2} minuses.
Note that:
- If the ācombinedā element is a plus in the final configuration, it then contributes to two pluses and one minus.
Apart from it, the number of pluses and minuses will be equal, so the hypothesis holds. - If the combined element is a minus in the final configuration, the hypothesis still holds: the negative part of it will become a plus in the final configuration, while the positive parts become minuses.
As for the second claim, thereās a pretty simple construction that achieves it.
Every move, choose two elements that are pluses and one thatās a minus, and perform the operation using them - the new element should be designated a plus.
This characterization gives us a direct solution: \frac{N+1}{2} elements are added and the rest are subtracted, so of course to maximize the sum, the largest \frac{N+1}{2} elements should be added and the rest should be subtracted.
This can easily be found in \mathcal{O}(N\log N) time by just sorting the array.
Now, we know how to solve the task in \mathcal{O}(N\log N) time for a single query.
This solves the first subtask, but not the second.
To solve the second subtask, weāll instead just precompute the answers for each odd-length prefix, and look them up later.
Suppose we know the answer for the prefix of length i, meaning we know the split of the first i elements into large and small.
When A_{i+1} and A_{i+2} are added, not much changes really.
Specifically, suppose you store the ālargeā elements in a list L, and the āsmallā elements in another list S.
Note that L and S have the property that |L|-|S| = 1, and also \min(L)\geq \max(S).
These lists can then easily be updated as follows:
- Insert \min(A_{i+1}, A_{i+2}) into S, and \max(A_{i+1}, A_{i+2}) into L.
This keeps the sizes balanced. - Now, while \min(L) \lt \max(S), extract the minimum of L and the maximum of S, and put them into the other list.
- Make sure to maintain the sums of L and S while performing these operations, since in the end thatās what we really care about.
With a structure that supports quick insertion, deletion, and lookup of its minimum/maximum element (such as a priority queue or multiset), this takes \mathcal{O}(\log N) time per index, for \mathcal{O}(N\log N) time overall.
(Note that weāll only move a constant number of elements between lists at any index).
Queries can be answered in constant time after this is done.
This trick of maintaining two lists for large/small elements can also be seen in, for example, the streaming median problem.
TIME COMPLEXITY:
\mathcal{O}(N\log N + Q) per testcase.
CODE:
Tester's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define all(x) begin(x), end(x)
#define sz(x) static_cast<int>((x).size())
#define int long long
typedef long long ll;
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--) {
int n, q;
cin >> n >> q;
int a[n];
for (auto &x : a) cin >> x;
int ans[n];
multiset<int> s1, s2;
int sum1 = 0, sum2 = 0;
int i = -1;
for (auto u : a) {
i++;
s1.insert(u);
sum1 += u;
while (sz(s1) >= sz(s2)) {
int x = *s1.rbegin();
s1.erase(s1.find(x));
s2.insert(x);
sum1 -= x;
sum2 += x;
}
while (sz(s1) && sz(s2) && *s1.rbegin() > *s2.begin()) {
int x1 = *s1.rbegin();
int x2 = *s2.begin();
s1.erase(s1.find(x1));
s2.erase(s2.find(x2));
s1.insert(x2);
s2.insert(x1);
sum1 += x2 - x1;
sum2 += x1 - x2;
}
ans[i] = sum2 - sum1;
}
while (q--) {
int j;
cin >> j;
j--;
cout << ans[j] << " ";
}
cout << "\n";
}
}
Editorialist's code (Python)
from heapq import heappop, heappush
for _ in range(int(input())):
n, q = map(int, input().split())
a = list(map(int, input().split()))
ans = [0]*n
small, large = [], []
smallsm, largesm = 0, 0
ans[0] = a[0]
largesm = a[0]
heappush(large, a[0])
for i in range(2, n, 2):
x, y = min(a[i], a[i-1]), max(a[i], a[i-1])
heappush(small, -x)
smallsm += x
heappush(large, y)
largesm += y
while -small[0] > large[0]:
x, y = heappop(small), heappop(large)
x *= -1
smallsm -= x
largesm -= y
heappush(small, -y)
heappush(large, x)
smallsm += y
largesm += x
ans[i] = largesm - smallsm
answers = [0]*q
queries = list(map(int, input().split()))
for i in range(q):
x = queries[i]
answers[i] = ans[x-1]
print(*answers)