THROWTAKE - Editorial

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';
    }
}
2 Likes

https://www.codechef.com/viewsolution/66176075

Can anyone tell me any test case where my solution fails?

1 Like

In last paragraph, I don’t understand how will picking a coin force the other player to move the token away. This we proved only for odd c[i] only na?.

Since players only pick odd C_i, after picking that C_i becomes even, and the other player won’t pick it anymore.

3 Likes

What is wrong with my approach:

I store all values with odd c[i] in arr;
The player will choose the current maximum element in the array, then the next player will choose the maximum element in the subarray to right of previously chosen index. I store those values in array score.

The element in score at even index will be chosen by Alice and odd index by Bob, Bob can chose to deny everything and end. So we’ll take minimum at each step

Submission link : Solution: 66182684 | CodeChef

It will not always gives optimal result consider this case

4
1 1 1 1
4 7 6 5

In this case answer would be 5, if Alice select last pile at the beginning.

4 Likes

Can someone tell me why are we traversing from N to 1 instead of 1 to N. and why are we not applying dp seperately for alice and bob?

1 Like

Easy straight forrward Dp Solution:

  • See that we can cap each c[i] even->2, odd->1

  • dp[i][j][c] (i = {1…n}, j ={0(MN), 1(MX)), c={0…2} ) be a dp state which says if we are at i, want to min/max the difference based on j and current pile coin has c coin, what’s answer???

  • at each step either take coin from i position or don’t.

  • dp[i][MX][c] = max(dp[i+1][MX][c[i+1]] , dp[i][MN][c-1] + v[i]). // Don’t take , Take

  • dp[i][MN][c] = min(dp[i+1][MN][c[i+1]] , dp[i][MX][c-1] - v[i]). // Don’t take , Take

  • Final ans is dp[0][MX][c[0]]

States = n * 2 * 2 ~ O(n)

1 Like

I think that the solution won’t work for this test case.
5
2 5 4 1 1
49 24 17 54 23
Please can you confirm.

1 Like

1
3
1 1 1
92 73 16

correct output → 57
your output → 35

3 Likes

Suppose this is what you get after taking the maximum element
3
1 1 1
50 20 15
In this according to your logic, ans = 50-20+15 = 55, but once A takes 50, B will simply take 15,skipping 20 completely, therefore ans = 50-15 = 35.

2 Likes

Could some one please explain me where I am going wrong with the below way.
for the test case

6
1 2 5 1 1 3
38 46 66 64 59 69

the moves are as follows

  • Alice throws the first 3 piles and picks 4th one A = 64
  • Bob picks 5th one B = 59
  • In the last Alice (A-B)max = 69

so totally we get a maximum of 69 - 54 + 69 = 74

The move taken by Bob is not optimal, optimal move by Bob is to throw 59 and take 69.

Bob can perform better with 69.

1 Like

ooh yes got it right, completely forgot that “BOB wants to minimize the score as much as possible” Thanks

1 Like

@ersshiva , In your code, for the condition if (j==MX), why are you doing val[i] + go(i, …)

I am not able to figure why alice and bob will place the the token where C is odd.
Can anyone please explain?

6 lines solution (DP)
https://www.codechef.com/viewsolution/66275778

1 Like

because even after taking 1 from c[i] in MX, now situtation is MN but we can still take 1 from c[i] . Though that will cancel MX and we can skip that but i put it it to be on safer side.

1 Like

Let me try to explain an another simpler method:
Create a 2-DP and let’s denote
dp[i][0] = max answer for suffix starting from index i and current move is of Alice
dp[i][1] = max answer for suffix starting from index i and current move is of Bob

Base Cases :
dp[n-1][0] = ( C[n-1]&1 ? V[n-1] : 0 );
dp[n-1][1] = ( C[n-1]&1 ? -V[n-1] : 0 );
We will solve for 2 different scenarios ( whether C[i] is even or odd ).
Let’s take 1st scenario:
**C[i] is even : **
** dp[i][0] : (Alice move) **
Either throw some piles and then take next pile = max( dp[i+1][0] , dp[i+2][0] , …dp[n-1][0] ) = X
Or, take ith pile and now, next move is of bob :
Now bob has also 2 choices :
Choice 1 : throw some piles and then take next pile = min( dp[i+1][1] , dp[i+2][1] , …dp[n-1][1]) = Y
Choice 2 : take ith pile = -V[i]
So, dp[i][0] = max( X , min( V[i] + (-V[i]) , V[i] + Y) ) ;

**dp[i][1] : (Bob move) **
Either throw some piles and then take next pile = min( dp[i+1][1] , dp[i+2][1] , …dp[n-1][1] ) = P
Or, take ith pile and now, next move is of Alice :
Now Alice has also 2 choices :
Choice 1 :throw some piles and then take next pile = max( dp[i+1][0] , dp[i+2][0] , …dp[n-1][0]) = Q
Choice 2 : take ith pile = V[i]
So, dp[i][1] = min( P , max( -V[i] + V[i] , -V[i] + Q) ) ;

C[i] is odd
Now doing similarly as above , we will get :
dp[i][0] = max( X , V[i] + Y ) ;
dp[i][1] = min( P , -V[i] + Q ) ;

Hope , I have explained it .
Here is my code for reference : Solution: 66541045 | CodeChef

1 Like