PROBLEM LINK:
Author: Aditya Kumar
Tester: Dev Kumar
Editorialist: Aditya Kumar
DIFFICULTY:
MEDIUM
PREREQUISITES:
Dynamic Programming
PROBLEM:
Two players wanted to divide gem stones placed on a table among themselves to eat food. For this purpose they play a special game that they created. The players alternately take a positive number of gem stones from the table, but no more than some fixed integer. The player that empties the box eats food from the collected gem stones while the other guy puts his stones back on the table and the game continues with the looser player starting. The game continues until all the gem stones are used by the players for eating food. The goal is to eat maximum units food (one gem stone equals one unit of food. Also all the gem stones are symmetrical and have same properties). You need to tell how many units of food player 1 consume, if he starts first.
EXPLANATION:
At each state of the game we have n1, n2 and nb representing the number of gem stones with player 1, number of gem stones with player 2, and number of gem stones left on the table. So our DP has all together three states.
Initialize DP with -1 representing its value is not computed yet.
How to compute the DP[k][i][j]?
Let’s say we have a function f to compute DP[k][i][j]. So, if we have f we just need to print the value of DP[N][0][0] where N is the number of gem stones initially before game started.
Now, our task reduces to how to make the function f. The function f looks like this:
int f(int n1, int n2, int nb){
int &P = dp[nb][n1][n2];
if(P!=-1) return P; // We have computed the value before
if(n1==0 and n2==0 and nb==0){
P = 0; // We have no gemstones on the table and no gem stones with either of the players.
return P;
}
if(nb==0){
// No gem stones are left on the table
P = f(0, 0, n1); // The player that empties the box eats food from the collected gem stones while the other guy puts his stones back on the table and the game continues with the looser player starting
return P;
}
P = 0;
for(int i=1;i<=min(M, nb);i++){
int R = nb+n1+n2 - f(n2, n1+i, nb-i);
// R is number of stones player 1 gets by picking i stones from the table.
P = max(P, R);
}
return P;
}
OPTIMAL COMPLEXITY:
\mathcal{O}(N^{3}*M).
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution will be uploaded soon.