There is a game on a tree On each move a proper subtree(i.e. any subtree but not whole tree) has to be clipped off the tree
The player who can't make a move loses.
I am thinking in terms of grundy numbers for each subtree and since each children are independent so xoring all the Gs of them to get the G of root
But this does not seem to work and in the solution they are doing G(root) = XOR(G(1 + child_i)
I don't get it why this +1 is added before xor
Could not find any good explanatory tutorial on this.
Any explanation or redirection to any relevant resources will be appreciated
Auto comment: topic has been updated by sniper_0101 (previous revision, new revision, compare).
The same task with an editorial
Thanks
I think that +1 pops up because each child subtreee isn’t just an impartial game of siz G(child) you also get the extra move of choping that whole subtree off in one go (which sends its Grundy to 0). so from that component you can reach all the internal Grundies {0,…,G(child)–1} plus the remove entirely move to 0 making the mex = G(child)+1. that is why each branche is a Nim heap of size G(child)+ 1 and you XOR those to get G(root).
Look up the Sprague–Grundy theorem applied to subtraction/subtree‐removal games in any Combinatorial Game Theory text (i recomend : Winning Ways)
yeah I also observed that there is an extra option of move to remove the entire subtree 'i' and that sets G of subtree 'i' to 0. But Since 0,1,2,...gi-1 are coming as reachable states from internal moves in that subtree 'i' (and due to which the mex gi becomes the subtree's grundy) Here we already have 0 in this set right. What's the point of considering it again ?
And how does the heap of size gi+1 represent the same ? Why exactly the +1 ?
hmm its kinda weird to explain it in english but if a child subtre has Grundy number g its internale moves let you reachs positions with Grundy zero, one, two, up to g minus one and the one extra move of chopping off the entire subtree reaches Grundy zero as well so to model exactly those options in Nim you pick a heap of size g plus one:
from a heap of size g plus one you can reduce it to any heap size zero, one, two, up to g, which perfectly matches our subtree’s moves. By definition the mex of the set {0, 1, 2, …, g} is g plus one, so each branch has SG equal to g plus one. that is why you XOR g plus one for every child when computing the root Grundy.
is it clear for you brother?
Yes ! Finally got the idea. Thanks brother !
happy to help
Hello sir, I’m a first-year CSE student from NIT Rourkela. I really admire your CP journey. May I ask how you prepared for contests? And how were you able to solve like 10-12 problems a day, because I struggle to solve even 6 problems a day.
How does anyone consistently do 10-12 problems a day. That is just insanely impressive