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.
Tower Breakers, Again!
Tower Breakers, Again!
Sort by
recency
|
21 Discussions
|
Please Login in order to post a comment
Here is Tower Breakers Again problem solution in Python Java C++ and c programming - https://programs.programmingoneonone.com/2021/07/hackerrank-tower-breakers-again-problem-solution.html
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
!/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 count
if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')
My Code with comments : https://github.com/offamitkumar/HackerRank/blob/master/Algorithms/Game%20Theory/Tower%20Breaker%2C%20Again.cpp
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