Maverickk's blog

Dp Problem
By Maverickk, history, 9 years ago, In English

Alice and Bob are playing a game called "Stone Game". Stone game is a two-player game. Let N be the total number of stones. In each turn, a player can remove 1, 2 or 3 stones. The player who picks the last stone, loses. They follow the "Ladies First" norm. Hence Alice is always the one to make the first move. Your task is to find out whether Alice can win, if both play the game optimally.

I/P: 2 //testcases 1 3

O/P: No Yes

As I am just getting started in dp,I cannot think how I would build a table and store values.can anyone give me a hint?Thank You.

Tags dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

if N%4 != 1 Alice will win otherwise she will lose

→ Reply
»
9 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This isn't dp. If n % 4 != 0 then Alice will win. If n%4 !=0, first move you chose number n % 4. After that, if Bob remove x, Alice remove 4-x. The similar thnig if n % 4=0, only Bob will win.

→ Reply
  • »
    »
    9 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Firstly, Alice win if N%4 != 1 Secondly, this can be solved with dp, consider my comment below. And TS asked how to build dp solution.

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Sorry, my bad. I don't see, the player who removes the last stone loses. I thing that is normal game : who remove last stone it wins.

      Second, you can solve it with dp, but two things are imortant :

      1. Why you want dp, when you can solve it easier.

      2. Dp has complexity O(n), and solution can be O(1). I don't know constrains, but for n ≤ 109 solution below is wrong.

      → Reply
      • »
        »
        »
        »
        9 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        You may want to solve it exactly by dp approach simply to study dp. TS said that he is newbie in it and I assume he wants to improve dp skills other than finding formula which applies only to this problem.

        → Reply
»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

So, there is common dp solution for this kind of games.

let's have array bool dp[MAX_N]

  • Function: dp[i] determines if player whose turn wins when i stones left. (true=guarantee win, false=guarantee lose)
  • Base values: by the rules, if 0 stones left, player whose turn wins: dp[0]=true
  • Transitions: consider dp[i]. We have i stones left. After our turn our opponent will be in situation dp[i-1], dp[i-2] or dp[i-3]. So if one of that situations leads to lose, we choose it, and dp[i] leads to win. If they all lead to win, then we lose anyway. Thus dp[i] = !(dp[i-1]&&dp[i-2]&&dp[i-3])
  • Answer: obviously dp[N]

Example:

   i   0 1 2 3 4 5 6 7 8 
dp[i]  1 0 1 1 1 0 1 1 1

dp[0] = 1;
dp[1] = 0; //We have only one move, and it lead to 1, so it is losing position
dp[2] = 1; //We can take 1 stone to put opponent in losing position dp[1]
dp[3] = 1; //We can take 2 stones to put opponent in losing position dp[1]
dp[4] = 1; //We can take 3 stones to put opponent in losing position dp[1]
dp[5] = 0; //Doesn't matter how many stones we take we and up in winning position for opponent
dp[6] = 1; //We can take 1 stone to put opponent in losing position dp[5]
dp[7] = 1; //We can take 2 stones to put opponent in losing position dp[5]
dp[8] = 1; //We can take 3 stones to put opponent in losing position dp[5]

As you can see in this particular problem there is obvious pattern, which was mentioned by Outsider above, but as I said, this kind of dp approach(finding losing position for opponent) can be used in large amount of more complicated game problems.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    So for solving in dp: 1:check whether past values can be used for determining present value. 2:put base cases. 3:then finding relation to find the present value using past values. 4:get answer you want.

    Finding the relation to get values is hard to me in many problems.do you think more practice will help me get more comfortable with that?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      They say practice makes perfect. So yeah — more you solve — easier it becomes. Don't feel anything bad about something being hard — all competitive programmers were in such situation.

      I would recommend you start with standard dp problems such as LCS, LIS, Knapsack... (check out this entry)

      And then go to archive, choose dp tagged problems and sort them by amount of solutions — and solve them one by one. If you don't know how to — read editorial(which almost every problem has)

      Good luck!

      → Reply