- Practice
- Algorithms
- Game Theory
- Vertical Rooks
- Discussions

# Vertical Rooks

# Vertical Rooks

+ 4 comments I don't think this task is set up correctly. The problem states that both players play "optimally", but how the definite looser could play optimally? Optimal behaviour of definite looser is to make the game as long as possible (to reach to Apocalypse:)). The distances between board bounds and rook positions are not taken into account in reference implementation, and the looser (imagine it is the player who moves first, 2nd) may move his rook backwards (even if forward moves are possible) and change whole XOR-ing result finally.

Also, it looks like the comparison to NIM is incorrect, because in NIM you cannot put an item back (i.e., move backwards in VRooks).

+ 0 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.

#include <iostream> #include <vector> #include <ios> int abs(int x){ return x<0?-x:x; } int main(){ std::ios_base::sync_with_stdio(false); int t=0; std::cin >> t; while(t--){ int n=0; std::cin >> n; std::vector<int> r1; for(int i=0;i<n;++i){ int r=0; std::cin >> r; r1.push_back(r); } int total=0; for(int i=0;i<n;++i){ int r2=0; std::cin >> r2; total^=abs(r2-r1[i])-1; } std::cout << (total?"player-2\n":"player-1\n"); } }

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:

O O O B A

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

O O A O B

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

O A O O B

having a nimber of 2, and so on. Finally, we have

O O O A B

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

O O B O A

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.

+ 2 comments The problem says "In a turn, a player can move any of his VROOKs". That sounds like anywhere from 0 to N VROOKS can be moved in a turn. In which case, wouldn't Player 2 always win by moving all of their VROOKS adjacent to Player 1's VROOKS?

Must exactly 1 VROOK be moved on each turn?

+ 0 comments C# short:

`public static string verticalRooks(List<int> r1, List<int> r2) { return r1.Select((n,i)=>Math.Abs(n-r2.ElementAt(i))-1).Aggregate((cur,next)=>cur^next) == 0 ? "player-1" : "player-2"; }`

...as always.

+ 0 comments the way u can win the game is to move ur piece towards ur opponent's, from left to right, if there is no pieces that u can move, u failed. So we find first piece that can move towards opponent's, if not, find first piece that can move and move it. This is a way but hard to achieve. Maybe there is a better way that allow us not to move the piece.

Sort 16 Discussions, By:

Please Login in order to post a comment