PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: apoorv_me
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sorting, prefix sums
PROBLEM:
Alice and Bob play a game on array A, taking turns alternating moves. Alice goes first.
Alice also has a sequence B, initially empty.
Alice deletes an element from A and appends it to B on her turn.
Bob just deletes an element from A.
Alice must ensure that B is always sorted.
You’re also given S \in \{0, 1\}, Alice is allowed to skip her move if S = 1, and can’t if S = 0.
What’s the maximum sum(B) that Alice can attain, if Bob is playing to minimize it?
EXPLANATION:
We’ll solve S = 0 first, i.e, Alice can’t skip moves.
Suppose N is odd, say N = 2k+1.
Since Alice goes first, she must choose k+1 elements to append to B; Bob will delete the other k.
It’s not hard to see that Alice has to choose the smallest element at each stage; otherwise Bob can force her into a situation where she’s unable to make a move (and hence ends up with a score of 0).
How?
Let A be sorted in ascending order.
Suppose Alice doesn’t choose the smallest element, i.e, picks A_i where i\gt 1.
Bob will then pick A_{i+1} (unless i = N in which case Bob can pick A_2)
Alice is then forced to pick something at a position \gt i+1 to keep B sorted, and again Bob picks the element just after the one she chooses, and so on.
With this process, A_1 will never be picked, and it’ll eventually be Alice’s turn to make a move but she’ll be unable to pick anything that keeps B sorted, resulting in a score of 0.
Since Bob’s aim is to minimize Alice’s score, he can ensure that Alice is forced to pick the smallest k+1 elements (by just not choosing any of them on his turn, ensuring that Alice is forced to choose them all).
So, when S = 0 and N = 2k+1 is odd, Alice’s score is just the sum of the smallest k+1 elements of A, i.e,
Next, we look at what happens when N is even, say N = 2k.
It’s easy to observe that Alice’s first move must be to pick either A_1 or A_2 (A being sorted).
This is because, if something at index \gt 2 is chosen, Bob can employ a similar strategy as earlier to force Alice’s score to become 0.
If Alice picks A_2 first, note that this is essentially the same as playing the game on an array of size N-1 (considering the last N-1 elements of A), since A_1 can be entirely ignored henceforth.
This is an odd-sized array, and we know how to compute Alice’s score on it from above — it’ll be
What about A_1?
As it turns out, it’s never optimal for Alice to start with A_1.
Why?
If Alice picks the smallest element, Bob can pick the largest element; and we’re back to the same game but on a smaller array of even length.
There are two possibilities:
First, Alice can at some stage “skip” the smallest element, and we know from earlier than she must then choose the second smallest element.
Suppose Alice skips A_i to take A_{i+1} instead.
Then, as noted above the resulting game is equivalent to an odd-length one, whose solution we know: Alice should always pick the smallest remaining element, so after i+1 will choose the contiguous subarray ending at index k+1 (recall that N = 2k).
Alice’s score in this case will be A_1 + A_2 + \ldots + A_{i-1} + A_{i+1} + A_{i+2} + \ldots + A_{k+1}.
In other words, it’s the sum of the first k+1 elements, minus A_i.
Clearly, to maximize this we should skip i=1 so that A_1 is subtracted.
The second possibility is that Alice never skips the smallest element, and so she’ll end up with the sum of the smallest k elements, A_1 + A_2 + \ldots + A_k.
This is clearly inferior to the score obtained by skipping the first element, since we end up with A_1 instead of A_{k+1} and everything else remains the same.
The answers for both the even and the odd cases can be easily computed in \mathcal{O}(N\log N) time by sorting the array and then summing up the required range of elements.
Now, let’s extend the above result to S = 1.
Alice is allowed to skip moves now, but nevertheless under optimal play she’ll choose some contiguous range of elements.
If Alice’s first move is to pick A_i, then the elements before it can be essentially discarded; at which point the game is essentially being played on the suffix starting from index i.
This, we know how to solve from the S = 0 case, with the answer depending on the length of the suffix.
So, simply solve for each suffix and take the maximum of them all!
Proof of Alice choosing a contiguous range
We prove this by inducting on the length of A.
For N = 1, the claim is trivially true, so consider N\gt 1.
If Alice doesn’t choose A_1, then it can be ignored entirely, and the game is played on the suffix of length N-1 starting from index 2.
By the inductive hypothesis, the claim is true for this suffix.
So, we only need to deal with the case where Alice does indeed choose A_1.
Suppose Alice’s chosen elements don’t form a contiguous range, i.e, there exist indices i\lt j such that A_i is not chosen but A_j is.
Consider the smallest such pair of indices (i, j).
Alice’s first i-1 moves will of course be to choose the elements A_1, A_2, \ldots, A_{i-1}.
Then, there are two possibilities:
- First, Bob might have discarded A_i on one of his moves, making it unavailable for Alice.
He could’ve instead discarded A_j (and keep all other moves the same), which can’t increase Alice’s score; so discarding A_i is not optimal for Bob and he’d never do it. - This leaves the only other possibility: Alice voluntarily skipped all the elements from indices i to j-1.
But then, on the move when she chose A_{i-1}, she could’ve chosen A_{i} instead; and keep all the other moves the same.
This leads to a not-lower score, while also reducing i by one.
Repeat the process in the second step till eventually we reach i=1 meaning A_1 wasn’t chosen after all; and Alice’s solution is still optimal.
So, if A_1 is chosen, Alice’s optimal strategy will be to pick a contiguous subarray including it, as claimed.
The answer for a single suffix is the sum of a contiguous range of elements, which can be found in \mathcal{O}(1) time with the help of prefix sums.
TIME COMPLEXITY:
\mathcal{O}(N\log N) per testcase.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
#define f first
#define s second
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
int s;
void Solve()
{
int n; cin >> n;
vector <int> a(n);
for (auto &x : a) cin >> x;
sort(a.begin(), a.end());
int ans = 0;
if (s == 0){
int x = 1 + (n / 2);
for (int i = 0; i < x; i++){
ans += a[i];
}
if (n % 2 == 0) ans -= a[0];
cout << ans << "\n";
return;
}
int l = n - 1, r = n - 1;
int sum = a[n - 1];
ans = sum;
while (l > 1){
l -= 2;
sum += a[l] + a[l + 1];
sum -= a[r];
r--;
ans = max(ans, sum);
}
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
cin >> t >> s;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Tester's code (C++)
#ifndef LOCAL
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt,fma")
#endif
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#include "../debug.h"
#else
#define dbg(...) "11-111"
#endif
struct input_checker {
string buffer;
int pos;
const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";
input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}
int nextDelimiter() {
int now = pos;
while (now < (int) buffer.size() && !isspace(buffer[now])) {
now++;
}
return now;
}
string readOne() {
assert(pos < (int) buffer.size());
int nxt = nextDelimiter();
string res;
while (pos < nxt) {
res += buffer[pos];
pos++;
}
return res;
}
string readString(int minl, int maxl, const string &pattern = "") {
assert(minl <= maxl);
string res = readOne();
assert(minl <= (int) res.size());
assert((int) res.size() <= maxl);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}
int readInt(int minv, int maxv) {
assert(minv <= maxv);
int res = stoi(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
long long readLong(long long minv, long long maxv) {
assert(minv <= maxv);
long long res = stoll(readOne());
assert(minv <= res);
assert(res <= maxv);
return res;
}
auto readInts(int n, int minv, int maxv) {
assert(n >= 0);
vector<int> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readInt(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
auto readLongs(int n, long long minv, long long maxv) {
assert(n >= 0);
vector<long long> v(n);
for (int i = 0; i < n; ++i) {
v[i] = readLong(minv, maxv);
if (i+1 < n) readSpace();
}
return v;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int32_t main() {
ios_base::sync_with_stdio(0); cin.tie(0);
input_checker input;
int S, limitn = 0;
auto __solve_testcase = [&](int testcase) -> void {
int n = input.readInt(1, (int)1e5); input.readEoln();
limitn += n;
vector<int> a = input.readInts(n, 1, (int)1e9); input.readEoln();
sort(a.begin(), a.end());
vector<long long> pf(n + 1);
for(int i = 0 ; i < n ; ++i)
pf[i + 1] = pf[i] + a[i];
if(S == 0) {
int chs = (n + 1) / 2;
int st = n % 2 == 0;
cout << pf[st + chs] - pf[st] << '\n';
return;
}
long long res = 0;
for(int i = n - 1 ; i >= 0 ; --i) {
int r = (n - i + 1) / 2;
res = max(res, pf[i + r] - pf[i]);
}
cout << res << '\n';
};
int no_of_tests = input.readInt(1, (int)2e4); input.readSpace();
S = input.readInt(0, 1); input.readEoln();
for(int test_no = 1 ; test_no <= no_of_tests ; test_no++)
__solve_testcase(test_no);
assert(limitn <= (int)3e5);
input.readEof();
return 0;
}
Editorialist's code (Python)
t, s = map(int, input().split())
for _ in range(t):
n = int(input())
a = sorted(list(map(int, input().split())))
for i in range(1, n): a[i] += a[i-1]
ans, sub = 0, 0
for i in range(n):
L = (n-i+1)//2
if i%2 != n%2 and (s == 1 or i <= 1): ans = max(ans, a[i+L-1] - sub)
sub = a[i]
print(ans)