# Bitter Chocolate

# Bitter Chocolate

romanandreg + 0 comments 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)

xor0110 + 1 comment Interesting problem, that was fun!... Or maybe it's just me finally starting to learn DP. :)

mauricepatel37 + 1 comment 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.

paulpach + 0 comments Here is the logic in a nutshell:

**SPOILER ALERT**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.

for example:

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.

Another example:

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

Sort 3 Discussions, By:

Please Login in order to post a comment