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.
straightforward O(N) solution using cumulative XOR of Sprague-Grundy nimbers; passes all test cases. It turns out that the nimber for each column is just abs(row1-row2)-1. See at the bottom for a sketch of why this is the nimber.
Let's see why the nimber for each column is abs(row1-row2)-1. Remember, the nimber is defined as the smallest non-negative integer not equal to any of the nimbers of positions reachable from the current position. First, suppose N=5, and our column looks like this:
OOOBA
where O is an empty space, A stands for player-2, the first person to move, and B stands for player-1, the second (awful nomenclature). Here, A has already lost, so the nimber for this is 0. Now let's examine
OOAOB
Since the A can move down one spot and reach B's 0 nimber position, we assign nimber=1 to this. Similarly, we have this position
OAOOB
having a nimber of 2, and so on. Finally, we have
OOOAB
having nimber of 0, since none of the positions in can reach by a single move will result in B having a nimber 0. Next, we have
OOBOA
Having a nimber of 1, since A can move up one spot and reach B's 0 nimber position. This analysis can be continued easily, and we see that the nimber is abs(row1-row2)-1.
Vertical Rooks
You are viewing a single comment's thread. Return to all comments →
straightforward O(N) solution using cumulative XOR of Sprague-Grundy nimbers; passes all test cases. It turns out that the nimber for each column is just abs(row1-row2)-1. See at the bottom for a sketch of why this is the nimber.
Let's see why the nimber for each column is abs(row1-row2)-1. Remember, the nimber is defined as the smallest non-negative integer not equal to any of the nimbers of positions reachable from the current position. First, suppose N=5, and our column looks like this:
where O is an empty space, A stands for player-2, the first person to move, and B stands for player-1, the second (awful nomenclature). Here, A has already lost, so the nimber for this is 0. Now let's examine
Since the A can move down one spot and reach B's 0 nimber position, we assign nimber=1 to this. Similarly, we have this position
having a nimber of 2, and so on. Finally, we have
having nimber of 0, since none of the positions in can reach by a single move will result in B having a nimber 0. Next, we have
Having a nimber of 1, since A can move up one spot and reach B's 0 nimber position. This analysis can be continued easily, and we see that the nimber is abs(row1-row2)-1.