HackerRank: Vertical Rooks

HackerRank: Vertical Rooks

In HackerChess, there is a special piece, known as the VROOK. A VROOK is like a normal Rook, except that it can move only along the column. A VROOK can't capture/kill another VROOK, and it also can't jump over another VROOK.

HackerChess is played as follows. The board is an NxN grid. It is played between two players. Each column of the board contains exactly 2 VROOKs, one of player-1 and the other of player-2. Each player has N VROOKS, arranged on the board. In a turn, a player can move any of hisVROOKs, (i.e) if there are any possible VROOKs belonging to the player that has a position to which it can be moved. The player to make the last move wins.

Given an initial configuration of the board. If both player-1 and player-2 play optimally. Who will win the game, if player-2 gets to move first?

The game is similar to Northcott's variant of the Nim game. One could imagine this game as a regularNim game having N heaps, with each heap size being the distance between two vrooks.

Hence the game in question can be boiled down to an array of integers containing the sizes of each heap. In one move we can reduce one of the heap's size by any amount. Thus xor of all the heap sizes will tell us who will win the game, if it's zero the person who moves first, in our case player-2, will lose as he has no moves to make.

One might argue as to why this is Nim since the size of heaps can be increases, but you should know that the next player can make a move to reduce the size of the heap by exact same amount as made by the previous player until one reaches the end of the board making it just like Nim.

int main() {
    int nt, n;
    scanf("%d", &nt);
    while(nt--) {
        scanf("%d", &n);
        fprintf(stderr, "N = %d\n", n);
        for(int i=0;i<n;i++) {
            scanf("%d", &A[i]);
            if(n==3) {
                fprintf(stderr, "%d\n", A[i]);
            }
        }

        for(int i=0;i<n;i++) {
            scanf("%d", &B[i]);
        }
        int nimber = 0;
        for(int i=0;i<n;i++) {
            int heap = abs(B[i] - A[i]) - 1;
            nimber ^= heap;
        }
        puts(nimber?"player-2":"player-1");
    }
    return 0;
}

static void solve()
{
for(int T = ni();T >= 1;T--){
int n = ni();
int[] a = na(n);
int[] b = na(n);
int win = 0;
for(int i = 0;i < n;i++){
win ^= Math.abs(a[i]-b[i])-1;
}
if(win == 0){
out.println("player-1");
}else{
out.println("player-2");
}
}
}