×

RRTREGAM - Editorial

Author: Aniket Marlapalle
Tester: Harsh Shah
Editorialist: Harsh Shah

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

5★begin_hs
573
accept rate: 0%

19.5k348496537

 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×1,572
×138
×37
×21
×4
×1

question asked: 09 Nov '16, 22:32

question was seen: 489 times

last updated: 07 Jun '17, 17:18