How to improve this Dynamic Programming solution?

Question

Original problem statement Pile it up

Summary: Two player A and B play a game consisting of 2 piles of X and Y coins. Each turn he can do one of the following:

Remove any number of coin from a single pile (at least 1 coin)
Remove the same amount of coin from both pile
Pass the turn. This still count as one turn.

The game ends when no move is possible and the player who cannot make a move loses. Both players play optimally. Both players calculate the outcome of the game before the game begins. The player who loses tries to maximize the number of turns in the game and player who wins tries to minimize the turns. No player can pass more than P times. A starts the game. Output the name of the winner and the number of moves in the game separated by a single space. 0 <= X, Y, P <= 1000

I came up with an O(n^3) DP solution but surely it is not good enough for this problem considering the bounds. Let d[i, j] be the minimum number of turns to win if this is your turn to play and there are i and j coins left in pile X and Y respectively. Then we have:

d[i, j] = 0 if i = j = 0
          1 if (i = 0 && j > 0) or (i > 0 && j = 0) or (i = j && i > 0)
          min(min(d[i-p, j]), min(d[i, j-q), min(i-r, j-r)) if a each substate is a losing position
          max of all winning position substate if no losing substate is found

Finally, d[i,j] = d[i,j] + 2*P if [i,j] is a winning state and you will not win immediately from the start.

As you can see from the formulation above, this is a O(n^3) solution. I want to improve my solution to O(n^2), how can I reformulate the problem?

The “aim of this game” paragraph doesn't make sense; please edit question and fix it. You probably mean player A where you wrote winner and player B where you wrote loser. — James Waldby - jwpat7
@Aravind:i and j are the remaning number of coins in pile X and Y. — Minh Pham
@sowrov: if he does so, the second player to move will take whatever remaining of the nonempty pile and win, hence he will not lose. Therefore the first person to move will not make such a move, rather he will figure how to win, or how to delay the victory of the other. — Minh Pham

Aravind Aravind · Accepted Answer · 2013-07-08T06:45:28

First winning positions are

1 empty pile
two piles with same number of coins

When will a player pass his turn?
Suppose position is (3,2), then thre are 3 options for him.

He can move to (2,2) but that makes it a winning position for his opponent.
He can move to (1,0) but again that is a winning position for his opponent.
If he chooses to skip the turn, then opponent can skip the turn too.This skipping can go for P turns at most.

Depending on parity of P(whether P is even or odd) and depending on who starts the skipping sequence, we can find out the person who won.Finding the number of turns isn't much harder from there.

Why is the skipping sequence optimal?
Well if you are losing you would want to stay in the game longer.(As given in rules of the game.)So even though I know based on the parity of P that I am going to lose, I can delay it by P turns.Make sense?
I encourage you to use this insight into making your algorithm faster, but please do ask questions if you have trouble implementing it!

How to improve this Dynamic Programming solution?

1 Answers