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.
Assuming you know very well about finding grandy value of every state .
Now think about , a normal number 105 .
Its all divisors are
1, 3, 5, 7, 15, 21, 35, 105
So , Our tower with height(105) can be broken into 105/Z=35(Y) towers with all have equal size Z=3 . So grandy value of a state is the mex of all the possible states which can be reached by a valid move (mex is the minimum state that is not possible to be reached from that particular state ) .
Here , when we will break a tower (105) into 35(Y) towers with size of all 3(Z) .Then the grandy value of (105) will be G(105).
Where G(105) will be xor of all other grandy value of child towers of this father tower .
G(105) = G(3) ^ G(3)^G(3)^G(3)......... till 35(Y) times . But we can easily catch that if Y is odd then no need to xor of all Z . It will be obviously only G(3) as rest of all are even in number ( canceled out by the xor ) .
So , G(105)= G(3) when , we will break it into 35(Y) towers with size of all 3(Z) only and not take other possible state's grandy vale .
But we can break it into its all divisors according to question . More fromally ,we have to take into account all possible state's grandy value .So use sieve to calculate all divisors of a number till 100000 previously. Now according to question grandy of (105) will be mex of the set { G(1), G(3),G( 5), G(7), G(15), G(21), G(35),G( 105 ) } and another fact is when Y will be even for any Z ,then Xor will be zero i.e. G(Z) =0 . I hope all are clear . My pseudocode to find grandy recursively
`intsg(intX){if(X==1)/// when the{return0;}if(grandy[X]!=-1)/// if grandy value is already computed just return it , no need to calculate it{returngrandy[X];}set<int>s;for(inti=0;i<divisors[X].size();i++){intY=divisors[X][i];/// the tower will be broken down into Y towers ,Y>1/// 1 is not included into any number's list of divisors during sieve ,so this Y will not be 1 neverintZ=X/Y;/// Each of Y towers has height of Z , may be also height of 1 which will terminate our program by finding our grandy value of every X,as X=1 is base condition .if(Y%2==0)/// The number of towers are even then ,obviously its all tower's size will be canceled out as being of equal,grandy value will be 0 .s.insert(0);else/// The number of towers are odd,obviously take only grandy value of one tower's size (Z).rest of the towers are canceled out by each other for xor technique.s.insert(sg(Z));}intmex=0;while(s.find(mex)!=s.end())mex++;///checking which smallest number not included in the set.grandy[X]=mex;///assigning mex[not included minimum element in the set of grandy value of possible towers]returngrandy[X];/// return grandy}`
Tower Breakers, Again!
You are viewing a single comment's thread. Return to all comments →
Assuming you know very well about finding grandy value of every state . Now think about , a normal number 105 .
Its all divisors are
1, 3, 5, 7, 15, 21, 35, 105
So , Our tower with height
(105)
can be broken into105/Z=35(Y)
towers with all have equal sizeZ=3
. So grandy value of a state is the mex of all the possible states which can be reached by a valid move (mex is the minimum state that is not possible to be reached from that particular state ) .Here , when we will break a tower
(105)
into35(Y)
towers with size of all3(Z)
.Then the grandy value of(105)
will beG(105)
.Where
G(105)
will be xor of all other grandy value of child towers of this father tower .G(105)
=G(3)
^G(3)
^G(3)
^G(3)
......... till35(Y)
times . But we can easily catch that ifY
is odd then no need to xor of allZ
. It will be obviously onlyG(3)
as rest of all are even in number ( canceled out by the xor ) .So ,
G(105)
=G(3)
when , we will break it into35(Y)
towers with size of all3(Z)
only and not take other possible state's grandy vale .But we can break it into its all divisors according to question . More fromally ,we have to take into account all possible state's grandy value .So use sieve to calculate all divisors of a number till
100000
previously. Now according to question grandy of(105)
will be mex of the set {G(1), G(3),G( 5), G(7), G(15), G(21), G(35),G( 105 )
} and another fact is whenY
will be even for anyZ
,then Xor will be zero i.e.G(Z) =0
. I hope all are clear . My pseudocode to find grandy recursivelyMy full solution here :- https://github.com/joy-mollick/Game-Theory-Problems/blob/master/HackerRank-Tower%20Breakers%2C%20Again!.cpp
should