Link to the problem: B - ゲーム
My approach: This problem is similar to the Deque problem from Educational DP contest (L - Deque). 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 
, 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?
Is it possible to read the statement in English 
. I cannot find the translate button for the statement. It just translates the WebUI.
2 Likes
@aneee004 Open the problem page and there you can find the translate option after the URL towards the top-right corner. 
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
Someone really needs to translate atcoder problems, They are gold.
2 Likes
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
Ohh! I didn’t know. I was talking about Chrome.
1 Like
And write some editorials for them if possible. 
Awesome ! 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?
@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?