# Tower Breakers, Again!

# Tower Breakers, Again!

+ 0 comments I did not see anything in the problem statement that the tower has to be broken into prime numbers first. Where is that from? thanks

+ 0 comments # !/bin/python3

import os import sys import math #

# Complete the towerBreakers function below.

# def towerBreakers(arr): # # Write your code here. # d=0 for x in arr: d^=primeFactors(x) if(d!=0): return 1 else: return 2

def primeFactors(n): count=0 flag= True while n % 2 == 0: if(flag): count+=1 flag=False n = n / 2 for i in range(3,int(math.sqrt(n))+1,2): while n % i== 0: count+=1 n = n / i

if n > 2: count+=1 return countif

**name**== '**main**': fptr = open(os.environ['OUTPUT_PATH'], 'w')`t = int(input()) for t_itr in range(t): arr_count = int(input()) arr = list(map(int, input().rstrip().split())) result = towerBreakers(arr) fptr.write(str(result) + '\n') fptr.close()`

+ 0 comments

+ 0 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 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`int sg(int X) { if(X==1)/// when the { return 0; } if(grandy[X]!=-1)/// if grandy value is already computed just return it , no need to calculate it { return grandy[X]; } set<int>s; for(int i=0;i<divisors[X].size();i++) { int Y=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 never int Z=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)); } int mex=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] return grandy[X];/// return grandy }`

My full solution here :- https://github.com/joy-mollick/Game-Theory-Problems/blob/master/HackerRank-Tower%20Breakers%2C%20Again!.cpp

should

+ 0 comments "assuming both players always move optimally?"

I'm guessing '

**optimally**' here is not to end the game the quickest, ie each player converts the towers higher then or equal to 2 into the same number of towers of height 1 in turns. '**optimally**' actually means, each player needs ensure the longevity of each game and break the towers into largest hights possible within the given rules.

Sort 20 Discussions, By:

Please Login in order to post a comment