Sort 3 Discussions, By:
Please Login in order to post a comment
Why is the optimal choice of P1 not to always start with position (2, 1)? I don't understand why on the second example P1 starts on (1, 2) instead of (2, 1)
Why is 24 13 13 lose? P1 can reduce it to 24 13 11 and P2 cannot win this combo
My algo shows, that 24 13 11 is win position, so P2 will win. But I don't know exactly how :)
next turn will be 22 13 11 and it's lose position [for P1]
Interesting problem, that was fun!... Or maybe it's just me finally starting to learn DP. :)
Can you please explain the logic, why does this works? I tried to look at editorial and setter's code. But couldn't understand it since I don't know functional programming.
Here is the logic in a nutshell:
Each state is defined by 3 numbers (row1, row2, row3) and will have the value of either "win" or "lose".
The fundamental state is (0,0,0) with a value "win"
Now at any given state, you can have a number of moves which will transition to another state. For example, the state (2,2,1) has the following possible moves:
moves (2,2,1) = [(0,0,0),(1,1,1),(2,0,0),(2,1,1),(2,2,0)]
A state (row1, row2, row2) is a win if there is a possible transition to a lose state.
moves (1,0,0) = [(0,0,0)]
(0,0,0) -> win
There is only 1 move from (1,0,0), and that move happens to be a win. Since all the moves from (1,0,0) are wins, then (1,0,0) is a lose.
moves (2,0,0) = [(0,0,0), (1,0,0)]
(0,0,0) -> win
(1,0,0) -> lose
Since there is one move you can make from (2,0,0) that is a lose, then (2,0,0) is a win.
Many moves overlap, the moves from (10,10,10) have a massive overlap with the moves from (9,9,9), and each move would have to recursively calculate if it is a win or lose. This can be efficiently solved by memoizing the wins/loses for every state, so every state is only calculated once.
No more comments