We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
The editorial for this problem is both needlessly complex and provides a sub-optimal recursive solution for this problem in O(n^2) when it can be solved far more simply in O(1)
Start by mapping out the win states for the first and second players. Starting at the top left, the second player (S) wins in the square of 4 spaces by default, since first player (F) has no moves. From there propogate outwards and mark each square with the approprite win state.
01234567...0SSFFSSFF1SSFFSSFF2FFFFFFFF3FFFFFFFF4SSFFSSFF5SSFFSSFF6FFFFFFFF7FFFFFFFF*..# *if board were 8x8, this corner would be S.
The pattern becomes clear, if we shift the indicies down by 1 (start at 0), then the second player only wins if the coin starts at a space where (x//2)%2==0 and (y//2)%2==0, otherwise the first player wins. The code is relatively trival. (Note that there is one corner case that could arise at the bottom right corner of the board depending on the size of the board, but in the 15x15 case this is not an issue).
A Chessboard Game
You are viewing a single comment's thread. Return to all comments →
The editorial for this problem is both needlessly complex and provides a sub-optimal recursive solution for this problem in O(n^2) when it can be solved far more simply in O(1)
Start by mapping out the win states for the first and second players. Starting at the top left, the second player (S) wins in the square of 4 spaces by default, since first player (F) has no moves. From there propogate outwards and mark each square with the approprite win state.
The pattern becomes clear, if we shift the indicies down by 1 (start at 0), then the second player only wins if the coin starts at a space where (x//2)%2==0 and (y//2)%2==0, otherwise the first player wins. The code is relatively trival. (Note that there is one corner case that could arise at the bottom right corner of the board depending on the size of the board, but in the 15x15 case this is not an issue).