PROBLEM LINKS
DIFFICULTY
EASY
EXPLANATION
The problem saw a lot of successful submissions with mostly the same approach(but different implementations).
This problem is a simple application of Sprague-Grundy theorem (http://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem) .
It is easy to see that if a coin is at (i,j) on a board with dimensions n x m, it is equivalent to the coin being on a board with dimensions (n-i) x (m-j). It means we can replace the board with a new board of dimensions (n-i) x (m-j). So we can look at it as a game where the given boards are getting smaller and smaller with every move until the size of the all the boards becomes 1x1.
We can associate grundy number with a board of dimensions n x m. Let g[n][m] be the grundy number associated with a board of dimension n x m. The board can be “resized” according to any of the VALID moves. So using the property of grundy numbers (http://en.wikipedia.org/wiki/Grundy_number) we can easily see that:
g[n][m] = mex( g[n-1][m], g[n-2][m], g[n-1][m-1], g[n-2][m-2], g[n][m-1], g[n][m-2])
Now, once we have the grundies of every given board, g[n1][m1] XOR g[n2][m2] XOR … XOR g[nc][mc] = 0 will tell us that the brother wins. If it is non-zero, our Chef wins!
Calculating the grundy numbers for every test case will give a TLE. If you observe carefully, the grundy numbers associated with every dimension will remain the same (i.e. do not depend on the test case). So we can precompute all the grundy numbers and use these values later.
The time limit for this problem was a little on the relaxed side. The above approach would pass without any trouble. But a lot of users solved it using the following approach which uses lesser space and time.
This approach is based on a simple observation which is not hard to see (working out a few examples manually would help you see it). The observation being: Grundy number of any board will not exceed 2. More specifically, grundy of a board of dimensions of n x m will be given by:
(n+m-2)%3. We have the grundy of every board in O(1) time and space. We can proceed similar to the previous approach now.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.