PROBLEM LINKS
DIFFICULTY
MEDIUM
EXPLANATION
As usual this kind of games can be solved using Sprague-Grundy theory. However first we will have to find out how to calculate Sprague-Grundy values for the states of the game. In order to do this let’s describe the game more formally. As the squares don’t intersect for each square A we can determine the smallest enclosing square. We will consider the smallest enclosing square to be the parent of the square A. For some squares there will be no enclosing square. So they will have no parent. That way we build a forest of rooted trees with nodes being the squares and roots being the trees with no parents. Now the turn of the game will be choosing any node of any tree and removing the subtree with the root in this node.
Let’s divide the whole solution into 3 parts:
- Build the forest effectively.
- Calculate Sprague-Grundy value of the game.
- If the first player can win determine the winning move.
The first part can be done using sweep line algorithm. We will sweep over one of the axes. We will maintain the sorted list of tops and bottoms of all the squares that are currently intersected by the sweep line. When we come upon the left side of a square A we add its top and bottom to the list. Also in this case we should look at the previous element in the list for the bottom of our square. If this element is the bottom of a square B then the square B is the parent of the square A. If this element is the top of a square C then the parent of the square C is the parent of the square A. When we come upon the right side of the square A we remove its top and bottom from the list. Given that the add to list and remove from list operations are implemented with O(logn) complexity this part is O(nlogn).
When we have the forest built we can do the second part. Our game is actually Green Hackenbush on Trees. For this game it is known that each tree is equivalent of Nim-stack and the Sprague-Grundy value of the game is the Nim-sum of values of each tree. Now how to calculate the value of a tree. Let R be the root of a tree then the Sprague-Grundy value of the tree is 1 plus Nim-sum of the values of all its subtrees. The proof of this is left as an exercise. Knowing this we can derive an O(n) recursive algorithm to find the Sprague-Grundy of the game.
Now if the second player wins the game (i.e. the Sprague-Grundy value is 0) we just state this. If the first player can win (i.e. the value is not 0) we have to find a winning move. We can find all the winning moves in O(n) time using the method alike to determining the winning move for Nim. The method can be described as follows. Let the value of the game be S. In order to win we have to make a move to P-position (with 0 value). Let the value of some tree be T. We try to make a move in this tree so that its values becomes Q=S?T. If it were Nim-stacks we would just removed the needed amount of stones, but with trees it’s a little more complex. We will make a query to the tree if we can make its value equal to Q: makeTreeValue(tree, Q). The answer to the query will be the numbers of the nodes we need to remove to make the value of the tree equal to Q or -1 if it can’t be done . If Q is 0 that the answer is the root of the tree. Otherwise we need to make the Nim-sum of the subtrees equal to Q-1. Let the current Nim-sum of the subtrees be R. Then we ask all the subtrees the same query: makeTreeValue(subtree, (Q-1)?R) - and gather the answers. And we do this for all the trees in the forest. Also according to the problem statement we need to pick the winning move with the smallest number.
The overall complexity is O(nlogn).
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.