CODEWITHSUNDEEP
algorithmdynamic-programming
Minh Pham
Minh Pham

Reputation: 974

How to improve this Dynamic Programming solution?

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:

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?

Upvotes: 1

Views: 737

Answers (1)

Aravind
Aravind

Reputation: 3179

First winning positions are

  1. 1 empty pile
  2. 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.

  1. He can move to (2,2) but that makes it a winning position for his opponent.
  2. He can move to (1,0) but again that is a winning position for his opponent.
  3. 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!

Upvotes: 1

Related Questions