PROBLEM LINK:
Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Harsh Shah
DIFFICULTY:
EASY-MEDIUM
PREREQUISITES:
Game theory, Grundy numbers.
PROBLEM:
Given a rooted tree and some stones in some nodes. Two players play a game, with each player moving a couple of stones from a node to any of its ancestors. The player who can’t make a move loses. Find the winner if Rachel goes first.
EXPLANATION:
For simplicity, let’s divide the number of stones in each node by 2 (integer division). Hence now, in a move a player moves a single stone to its ancestor. Now, when would the game end? It will end when no player is able to make a move i.e all the stones of the tree have reached the root node i.e. node 1. Hence every stone can be treated independent, and during the game it traverses its ancestor and finally reaches the root node.
Now let’s assign Grundy number to each stone. Since the game ends at root node, a stone in root node gets grundy number 0. Consider stone at a node N at depth 1. Since a player can move this node to only its only ancestor (root node), this stone gets grundy number 1. Generalizing this, a stone at depth d can be moved to any node at depth d-1,d-2,…0(root node) having grundy numbers d-1,d-2,…0 respectively. This node gets grundy number d. Hence we can conclude that the grundy number of a stone is equal to the depth of the node it resides in. Now we know that the first player wins if the xor of all the grundy number is not zero. (Refer to game theory and game theory basics for more clarification). Hence we have to find xor of grundy nunber of all stones. We know that, x xor x is 0. Hence a node having even number of stones has no contribution to the total xor computation, while a node at depth d having odd number of nodes contributes d to the xor computation. Refer the code for complete clarification.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here