TGOC - EDITORIAL

PROBLEM LINKS:

Contest

Practice

DIFFICULTY:

DIFFICULT

EXPLAINATION

The chess-game can be considered to two independent chess games, where in first only a knight is present and the queen in other.

Now each game is equivalent to single nim heap in the nim game.

Now we will calculate the grundy values for each game interdependently (which is the minimum excluded value, mex, for each position).

For Knight game, where knight is at (x, y),

grundyKnight(x, y) = mex(grundyKnight(x-1, y-2), grundyKnight(x-2, y-1))

Similarly for Queen game, with queen at (x, y)

grundyQueen(queen) = mex( grundyQueen(x-i, y), grundyQueen(x-i, y-i), grundyQueen(x, y-i)) , where 1 <= i <= 50

So the grundy value of both game combined (original game) is the nim sum of both games.

grundy(knight-game + queen-game) = grundyKnight(knight-position) xor grundyQueen(queen-position)

Since, according to sprague grundy theorem, the game can be won if grundy value is a positive value.

Refrence

Setters Solution

My dp solution: https://aleigorithms.wordpress.com/2015/09/18/coderush-2015/

@author: please, the statement of the problem is very incomplete !!! It should be stated that you can have two pieces on the same cell…

1 Like
//