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.
java solution, passes all test cases in O(k) time and O(1) space. First compute the nimber (e.g. Grundy number) for all 15 x 15=225 spots on the chess board. The nimber of a spot (x,y) is the smallest non-negative integer not equal to the grundy numbers of any of the up to four spots reachable from (x,y) in a single jump. This can be done in O(m^2) time, where m=15=O(1) in this problem, by filling in successive diagonals of the matrix of nimbers.
Once we have the nimbers of every spot on the chessboard, simply take cumulative XOR of all k nimbers. If 0, the first player loses, and if nonzero, the first player wins.
Chessboard Game, Again!
You are viewing a single comment's thread. Return to all comments →
java solution, passes all test cases in O(k) time and O(1) space. First compute the nimber (e.g. Grundy number) for all 15 x 15=225 spots on the chess board. The nimber of a spot (x,y) is the smallest non-negative integer not equal to the grundy numbers of any of the up to four spots reachable from (x,y) in a single jump. This can be done in O(m^2) time, where m=15=O(1) in this problem, by filling in successive diagonals of the matrix of nimbers.
Once we have the nimbers of every spot on the chessboard, simply take cumulative XOR of all k nimbers. If 0, the first player loses, and if nonzero, the first player wins.