PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: wuhudsm
Tester: mexomerf
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Dynamic programming, prefix sums, observation
PROBLEM:
Alice and Bob play a game on two arrays, S_1 and S_2.
On their turn, a player choose either the minimum element of S_1 or the maximum element of S_2, adds it to their score, and deletes it.
Let A and B be Alice’s and Bob’s scores.
Alice plays to maximize A-B, Bob plays to minimize it.
Find the final value if they both play optimally.
EXPLANATION:
Notice that no matter what A and B are in the end, A+B is a constant, being the sum of all numbers in both arrays.
So, if S = A+B, we have A-B = A - (S-A) = 2A-S.
That is, maximizing A-B is equivalent to maximizing A; and similarly for Bob minimizing A-B is equivalent to maximizing B (which minimizes A).
Both players will thus play in order to maximize their scores.
For convenience, let’s sort S_1 in descending order and S_2 in ascending order, so that each move becomes “choose the last element of one of the arrays”.
After this, let P_{1, i} = S_{1, 1} + S_{1, 2} + \ldots + S_{1, i} denote the prefix sum array of S_1.
Define P_{2, i} for S_2 similarly.
There’s then a relatively straightforward (but slow) dynamic programming solution to this task.
Let f(i, j) denote the maximum value the current player can attain, if there are i elements left in S_1 and j elements in S_2. The value we want is f(N, M) (with the final answer being 2\cdot f(N, M) - S).
Then,
- If the current player chooses from S_1, they get S_{1, i}, and then the other player will get f(i-1, j); meaning the current player gets everything else.
That’s a total of P_{1, i} + P_{2, j} - f(i-1, j). - If the current player chooses from S_2, a similar analysis gives P_{1, i} + P_{2, j} - f(i, j-1) instead.
- So, f(i, j) = P_{1, i} + P_{2, j} - \min(f(i-1, j), f(i, j-1)).
This is \mathcal{O}(N\cdot M) though, which is too slow.
To optimize this, we need to make some observations about the game.
In particular, it can be seen that if i is even, f(i, j) can be determined directly!
How?
Claim 1: Suppose N and M are both even. Then, the maximum value attainable is
X = S_{1, N} + S_{1, N-2} + \ldots + S_{1, 2} + S_{2, M} + S_{2, M-2} + \ldots + S_{2, 2}.
Recall that S_1 is in descending order, while S_2 is ascending.
Proof
Bob can ensure that Alice can never get anything larger than this value, since:
- If Alice picks an element from S_1, he does the same.
- If Alice picks an element from S_2, he does the same.
Alice’s value A obtained via this strategy is exactly equal to the X in our claim, making it an upper bound.
On the other hand, Alice can ensure she always attains at least X with a similar strategy.
Alice first chooses S_{2, M}. Then,
- If Bob chooses from S_2, Alice does the same.
- If Bob chooses from S_1, Alice chooses from S_1.
Note that this way, Bob will get all the odd-index elements of S_2, while Alice gets all the even-index ones.
Further, the best Bob can do is ensure Alice gets all the even-index elements of S_1 (note that those are the smaller ones), and doing so gets Alice to X, so it’s a lower bound as well.
Claim 2: Suppose N is even and M is odd.
It’s then optimal to pick from S_2 (after which both are even and the solution is known from claim 1).
Proof
If Alice chooses from S_2 first, as per the first claim, her score will be
S_{2, M} + (S_{1, N-1} + S_{1, N-3} + \ldots + S_{1,1} + S_{2, M-2} + S_{2, M-4} + \ldots + S_{2, 1}).
If Alice chooses from S_1 instead, Bob also chooses from S_1. This repeats till eventually Alice is forced to choose from S_2 (since N is even).
Note that this way, Alice’s score from S_2 remains the same, but from S_1 she ends up with a worse score.
So, it’s not optimal to do this; and Alice never will — meaning she’ll choose from S_2 on her first move, as claimed.
To compute these quickly given i and j, all that’s needed is to maintain alternating prefix sums of both S_1 and S_2.
Notice that this means:
- If N is even, the answer can be computed directly.
- If N is odd, the only states our recursion ever needs to visit are f(N, j) and f(N-1, j), since once we reach f(N-1, j) further recursion is unnecessary.
This is only about 2M states!
This reduces the complexity of the solution to \mathcal{O}(N+M) which is obviously fast enough.
TIME COMPLEXITY:
\mathcal{O}(N + M) per testcase.
CODE:
Author's code (C++)
#include <map>
#include <set>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <cstdio>
#include <cstdlib>
#include <vector>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
typedef double db;
typedef long long ll;
typedef unsigned long long ull;
const int N=1000010;
const int LOGN=28;
const ll TMD=0;
const ll INF=2147483647;
int T,n,m;
int a[N],b[N];
int Sa[N],Sb[N];
int DP(int x,int y)
{
if(x>n&&y>m) return 0;
int res=-INF;
if((n-x+1)&1)
{
if(x<=n) res=max(res,a[x]-DP(x+1,y));
if(y<=m) res=max(res,b[y]-DP(x,y+1));
}
else
{
if((m-y+1)&1) res=((x&1)?-1:1)*(Sa[n]-Sa[x-1])+((y&1)?1:-1)*(Sb[m]-Sb[y-1]);
else res=((x&1)?1:-1)*(Sa[n]-Sa[x-1])+((y&1)?1:-1)*(Sb[m]-Sb[y-1]);
}
return res;
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) Sa[i]=Sa[i-1]+(i&1?1:-1)*a[i];
for(int i=1;i<=m;i++) Sb[i]=Sb[i-1]+(i&1?1:-1)*b[i];
printf("%d\n",DP(1,1));
}
return 0;
}
Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long readInt(long long l, long long r, char endd) {
long long x = 0;
int cnt = 0;
int fi = -1;
bool is_neg = false;
while (true) {
char g = getchar();
if (g == '-') {
assert(fi == -1);
is_neg = true;
continue;
}
if ('0' <= g && g <= '9') {
x *= 10;
x += g - '0';
if (cnt == 0) {
fi = g - '0';
}
cnt++;
assert(fi != 0 || cnt == 1);
assert(fi != 0 || is_neg == false);
assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
}
else if (g == endd) {
assert(cnt > 0);
if (is_neg) {
x = -x;
}
assert(l <= x && x <= r);
return x;
}
else {
assert(false);
}
}
}
string readString(int l, int r, char endd) {
string ret = "";
int cnt = 0;
while (true) {
char g = getchar();
assert(g != -1);
if (g == endd) {
break;
}
cnt++;
ret += g;
}
assert(l <= cnt && cnt <= r);
return ret;
}
ll cal(ll dpa[], ll dpb[], ll i, ll j, ll m){
ll res = dpb[j];
if((m-j)%2){
res -= dpa[i];
}else{
res += dpa[i];
}
return res;
}
ll cal1(ll dpa[], ll dpb[], ll i, ll m, ll a[], ll b[]){
if(i == m){
return dpa[0];
}
return max(a[0] - cal(dpa, dpb, 1, i, m), b[i] - cal1(dpa, dpb, i+1, m, a, b));
}
int main() {
ll t;// = readInt(1,200000,'\n');
cin>>t;
ll ns = 0, ms = 0;
while(t--){
ll n;// = readInt(1,600000,' ');
ll m;// = readInt(1,600000,'\n');
cin>>n>>m;
ns+=n;
ms+=m;
assert(ns <= 600000);
assert(ms <= 600000);
ll a[n];
ll b[m];
for(int i = 0; i < n; i++){
cin>>a[i];
// if(i != n-1){
// a[i] = readInt(1,1000000000,' ');
// }else{
// a[i] = readInt(1,1000000000,'\n');
// }
}
for(int i = 0; i < m; i++){
cin>>b[i];
// if(i != m-1){
// b[i] = readInt(1,1000000000,' ');
// }else{
// b[i] = readInt(1,1000000000,'\n');
// }
}
ll dpa[n+1]={},dpb[m+1]={};
for(int i = n-1; i > -1; i--){
dpa[i] = a[i] - dpa[i+1];
}
for(int i = m-1; i > -1; i--){
dpb[i] = b[i] - dpb[i+1];
}
ll ans;
if(n%2==0){
ans = cal(dpa,dpb,0,0, m);
}else{
ans = cal1(dpa, dpb, 0, m, a, b);
//cout<<cal(dpa, dpb, 1, 0, m)<<"\n";
}
cout<<ans<<"\n";
}
}