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.
if N%4 != 1 Alice will win otherwise she will lose
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.
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.
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 :
Why you want dp, when you can solve it easier.
Dp has complexity O(n), and solution can be O(1). I don't know constrains, but for n ≤ 109 solution below is wrong.
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.
So, there is common dp solution for this kind of games.
let's have array
bool dp[MAX_N]
dp[i]
determines if player whose turn wins wheni
stones left. (true
=guarantee win,false
=guarantee lose)dp[0]=true
dp[i]
. We have i stones left. After our turn our opponent will be in situationdp[i-1]
,dp[i-2]
ordp[i-3]
. So if one of that situations leads to lose, we choose it, anddp[i]
leads to win. If they all lead to win, then we lose anyway. Thusdp[i] = !(dp[i-1]&&dp[i-2]&&dp[i-3])
dp[N]
Example:
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.
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?
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!