PROBLEM LINK:
Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4
Setter: TheScrasse
Tester: Harris Leung
Editorialist: Trung Dang
DIFFICULTY:
2323
PREREQUISITES:
Dynamic Programming, Game
PROBLEM:
There is a line consisting of N piles of coins on the table. For each i (1 \le i \le N), the i-th pile contains C_i coins, each with value V_i. There is also a bin under the table.
Alice and Bob play a game, moving alternately. A move consists of two steps:
- Throw a prefix of the piles in the bin (the prefix can be empty). Then, if there are no coins left on the table, the game ends. Note that in this step, it is not allowed to throw away only some coins in a pile â the entire pile must be thrown into the bin.
- Take exactly one coin from the first (remaining) pile. Then, if there are no coins left on the table, the game ends.
Let A and B be the sum of the values of the coins taken by Alice and Bob, respectively.
The score of the game is AâB. Alice wants to maximize the score; Bob wants to minimize it.
Alice moves first. Whatâs the score of the game if Alice and Bob play optimally?
EXPLANATION:
The problem has this equivalent (and hopefully slightly easier) perspective:
We have a token that is initially placed at position 1. At each turn, each player does the following:
- Place a token onto some position greater or equals to the current position (possibly placing it at N + 1 which ends the game, or not moving the token).
- Take a coin from the pile at the current position of the token (if the pile is non-empty).
We have these two observations:
- Alice never wants to place the token at a position where C_i is even. This is because Bob can retaliate this play by simply not moving the token and take the coin at the same position (and doing it again and again until Alice canât take any coin from this position anymore).
- Similarly, when itâs Bobâs turn, he also doesnât want to place the token at a position where C_i is even.
From these two observations, we have the following two conclusions:
- We only care about piles with C_i odd in this game.
- It is always optimal for each player to move the token (since after the other playerâs previous move, the pile at the tokenâs position has an even amount of coins).
From this, we arrive at a natural dynamic programming solution: let f_i be the maximal score the current player can achieve if the token is current at position i. Initially we have f_{N + 1} = 0. There are two cases:
- The current player decides to move the token away from i first before choosing their coin. The answer in this case is f_{i+1}.
- The current player decides to pick a coin from the i-th pile, forcing the other player to move the token away. The answer in this case is V_i - f_{i + 1}.
Therefore f_i = \max\{V_i - f_{i + 1}, f_{i + 1}\}.
TIME COMPLEXITY:
Time complexity is O(N) for each test case.
SOLUTION:
Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<
#define INF (ll)1e18
#define mod 998244353
#define maxn 200010
ll i, i1, j, k, k1, t, n, m, res, flag[10], a, b;
ll c[maxn], v[maxn], dp[maxn];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> t;
while (t--) {
cin >> n;
for (i = 1; i <= n; i++) cin >> c[i];
for (i = 1; i <= n; i++) cin >> v[i];
dp[n + 1] = 0;
for (i = n; i >= 1; i--) {
if (c[i] % 2) dp[i] = max(dp[i + 1], v[i] - dp[i + 1]);
else dp[i] = dp[i + 1];
}
cout << dp[1] << nl;
}
return 0;
}
Tester's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e6+1;
int n,k;
ll a[N],b[N];
void solve(){
cin >> n;
for(int i=1; i<=n ;i++) cin >> a[i];
for(int i=1; i<=n ;i++) cin >> b[i];
ll ans=0;
for(int i=n; i>=1 ;i--){
if(a[i]%2==1) ans=max(ans,b[i]-ans);
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);
int t;cin >> t;
while(t--) solve();
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t; cin >> t;
while (t--) {
int n; cin >> n;
vector<int> c(n), a(n);
vector<long long> dp(n + 1);
for (int i = 0; i < n; i++) {
cin >> c[i];
}
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = n - 1; i >= 0; i--) {
dp[i] = dp[i + 1];
if (c[i] & 1) {
dp[i] = max(dp[i], a[i] - dp[i + 1]);
}
}
cout << dp[0] << '\n';
}
}