We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
You have to convert the game to nim. Since, a board is broken down into 2. So, let us assume the no. of piles to be 2.
Now, comes the no. of stones in each pile. That depends on how you split it up.
For a N X M board, you can either split it row wise or column wise.
Row-wise: N-1
Column-wise: M-1
Total no. of ways: N+M-2
So, for a N X M board, you need to check the xor of the grundy values of the two sub-rectangles and if there isn't a single combination that gives a non-zero value, then surely the first player looses.
Now comes the assigning of grundy number to each sub-rectangle-
Base Case: If there is no non-primes at all. Assign this a Grundy value=0.
For the rest, assign them a Grundy value equal to the mex of the set containing the combinations of all the spilts in it.
(Xor of the Grundy values of the individual triangles.)
So, the no. of splits can be considered the no. of stones in the rectangle or pile!
Hope that helps :)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Digits Square Board
You are viewing a single comment's thread. Return to all comments →
My thoughtprocess:
You have to convert the game to nim. Since, a board is broken down into 2. So, let us assume the no. of piles to be 2. Now, comes the no. of stones in each pile. That depends on how you split it up.
For a N X M board, you can either split it row wise or column wise.
Row-wise: N-1
Column-wise: M-1
Total no. of ways: N+M-2
So, for a N X M board, you need to check the xor of the grundy values of the two sub-rectangles and if there isn't a single combination that gives a non-zero value, then surely the first player looses.
Now comes the assigning of grundy number to each sub-rectangle-
Base Case: If there is no non-primes at all. Assign this a Grundy value=0.
For the rest, assign them a Grundy value equal to the mex of the set containing the combinations of all the spilts in it. (Xor of the Grundy values of the individual triangles.)
So, the no. of splits can be considered the no. of stones in the rectangle or pile!
Hope that helps :)