Help with AtCoder TPDC problem B-Game

general
, ,
#1

Link to the problem: https://atcoder.jp/contests/tdpc/tasks/tdpc_game
My approach: This problem is similar to the Deque problem from Educational DP contest (https://atcoder.jp/contests/dp/tasks/dp_l). Using similar ideas I formulated the following recurrence relation with two states i and j, where dp[i][j] is the maximum score Snuke can achieve with i number of elements in pile A and j number of elements in pile B,
dp[i][j] = max(A[i]+min(dp[i-2][j],dp[i-1][j-1]), B[j]+min(dp[i][j-2],dp[i-1][j-1]))

Since most of the times I use top-down approach I tried the same for this problem too. But, the problem is that I am finding it difficult to handle the base cases :slightly_frowning_face:, I am facing difficulty in transitioning towards the base case. One base case is when both the piles get empty, that is alright, but I am having difficulty in handling the cases where only one pile becomes empty or the number of elements becomes less than one in one or both of the piles.
I looked at some of the submissions but couldn’t find a solution which used top-down approach. Can anyone please share some ideas and code that uses top-down approach to solve this problem?

#2

Is it possible to read the statement in English :no_mouth:. I cannot find the translate button for the statement. It just translates the WebUI.

2 Likes
#3

@aneee004 Open the problem page and there you can find the translate option after the URL towards the top-right corner. :slightly_smiling_face:

#4

The language option in the website only toggles the WebUI buttons. If you’re talking about chrome translate, well, I don’t use Chrome. So I’ll need an external translate?

1 Like
#5

Someone really needs to translate atcoder problems, They are gold.

2 Likes
#6

There is a little trick with the zerosum games.

Let s_1 be score of player 1 and s_2 be the score of player 2. Instead of storing s_1 in each node, we can store s_1 - s_2.

This is equivalent because essentially it’s just 2s_1 - \sum A_i - \sum B_i. So maximising them is equivalent.

Now our relation is dp_{i,j}=\max(A_i - dp_{i-1,j}, B_j - dp_{i,j-1}).
This can be done easily with recursion.

Just notice that the final answer will be (dp_{a,b} + sum)/2

Code 
#include <iostream>
#include <bits/stdc++.h>
#define mp make_pair
#define pb push_back
using namespace std;
using ll = long long int;
void solve(){
    int a,b;
    cin>>a>>b;
    vector<int> pile1(a), pile2(b);
    int sum = 0;
    for(auto &x : pile1){
        cin>>x;
        sum+=x;
    }
    for(auto &x : pile2){
        cin>>x;
        sum+=x;
    }
    const int INF = 1e9;
    vector<vector<int>> dp(a+1, vector<int>(b+1, -INF));
    dp[0][0] = 0;
    function<int(int,int)> solve = [&](int i,int j){
        if(dp[i][j]!=-INF){
            return dp[i][j];
        }
        if(i){
            dp[i][j] = max(dp[i][j], pile1[a-i] - solve(i-1,j));
        }
        if(j){
            dp[i][j] = max(dp[i][j], pile2[b-j] - solve(i,j-1));
        }
        return dp[i][j];
    };
    solve(a,b);
    int ans = dp[a][b] + sum;
    ans/=2;
    cout<<ans<<"\n";
}
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    solve();
}
2 Likes
#7

Ohh! I didn’t know. I was talking about Chrome.

1 Like
#8

And write some editorials for them if possible. :smile:

#9

Awesome ! :smile: By the way, was there any way to solve the problem using my approach mentioned before? And, what are some good resources to learn about problems involving such games?

#10

@everule1, @aneee004 I have a doubt. Since dp[i][j] = max(A[i]-dp[i-1][j], B[j]-dp[i][j-1]), does this essentially mean that to find the maximum difference in score for Snuke i.e. dp[i][j] we also need to find the maximum for his opponent which is denoted by dp[i-1][j] and dp[i][j-1]? Because I think the meaning of the state changes after each move, we are maximizing different things in different moves. Am I getting the meaning of the recurrence right?