Given an m x n matrix, where m denotes thenumber of rows and n denotes the number of columns and in each cell a pile of stones is given. For example, let there be a 2 x 3 matrix, and the piles are:

$${\begin{bmatrix} 2 & 3 & 8 \\ 5 & 2 & 7 \end{bmatrix}}$$

That means that in cell(1, 1) there is a pile with 2 stones, in cell(1, 2) there is a pile with 3 stones, and so on.

Now Alice and Bob are playing a strange game in this matrix. Alice starts first and they alternate turns. In each turn, a player selects a row and can draw any number of stones from any number of cells in that row. But he/she must draw at least one stone. For example, if Alice chooses the 2^nd row in the given matrix, she can pick 2 stones from cell(2, 1), 0 stones from cell (2, 2), 7 stones from cell(2, 3). Or she can pick 5 stones from cell(2, 1),1 stone from cell(2, 2), 4 stones from cell(2, 3). There are many other ways but she must pick at least one stone from all piles. The player who can't take any stones loses.

Now if both play optimally who will win?

Input

Input starts with an integer T (≤ 100),denoting the number of test cases.

Each case starts with a line containing two integers: mand n (1 ≤ m, n ≤ 50). Each of the next m lines contains n space separated integers that form the matrix. All the integers will be between 0 and 10⁹ (inclusive).

Output

For each case, print the case number and Alice if Alice wins, or Bob otherwise.

Sample

Sample Input	Sample Output
Click to copy 2 2 3 2 3 8 5 2 7 2 3 1 2 3 3 2 1	Click to copy Case 1: Alice Case 2: Bob

Total Submissions

Users Tried

Users Solved

LOJ-1247 Matrix Game

Approch

We have given a N * M Grid. A player can remove any number of stone from any row. So a player can remove 1 to all stone from a row. We can assume all the stone in a row as a single pile of stone. Then we will get N pile of stone.Now we can calculate xor-sum of that pile and determine who is winner.

Lets assume now we have 4 pile { 9 , 7 , 11 , 5 }.

Lets convert them in Binary.

we can see every column has even number of 1. When a player remove some stones from pile he will remove a 1 from it and the xorsum of the piles will be > 0. First player will remove 8 stones from the first pile then the binary state will look like

Then 2nd Player can remove 8 stones from 3rd pile and make the xor sum again 0.

As they play the game optimally so when a player gets xorsum>0 he will always win.

More description can be found in this link.

Solution Code:

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
   int t;
   cin>>t;
   int tc=1;
   while(t--)
   {
       int n,m;
       cin>>n>>m;
       ll xorsum=0; //0 XOR A = A always.
       for(int i=0;i<n;i++)
       {
           ll sum=0;
           for(int j=0;j<m;j++)
           {
               int a;
               cin>>a;
               sum+=a;
           }
           xorsum^=sum; //Doing XORSUM
       }
       cout<<"Case "<<tc++<<": ";
       if(xorsum>0)
        cout<<"Alice" << "\n";
       else
        cout<<"Bob" << "\n";
   }
}

Tutorial source