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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Game Theory
  4. Tower Breakers - The Final Battle
  5. Discussions

Tower Breakers - The Final Battle

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 16 Discussions, By:

votes

Please Login in order to post a comment

  • vinodantony10
    2 years ago+ 1 comment

    The game isn't explained well ... In the last case H=2 so it's split into 1 and 1 P2 chooses the second tower so how did it become 2^2?

    10|
    Permalink
  • dingma129
    4 years ago+ 2 comments

    An O(1) python solution using O(1) space

    the idea is to use dynamic programming to find the maximal possible number d[n] such that P_2 will earn exact n coins

    by simple observation, d[130] is already over 1e20 > 1e18, so we only need to store the d[n] values up to n=130

    a reference for the recursive formula can be found here http://oeis.org/A006456

    import math
    from collections import defaultdict
    
    def F(n):
        if n in d:
            return d[n]
        else:
            temp=0
            for k in range(1,int(math.sqrt(n))+1):
                temp+=F(n-k**2)
            d[n]=temp
            return d[n]
        
    def towerBreakers(n):
        ans=0
        while d[ans]<n:
            ans+=1
        print(ans)    
    
    d=defaultdict(int)
    d[0]=1
    F(130)  #d[130]>10**18
        
    for _ in range(int(input())):
        towerBreakers(int(input()))
    
    2|
    Permalink
  • apandey0826
    2 years ago+ 1 comment

    According to problem statement x>=2 and k>= 1 and k<=x ;

    so for example if n=4; coin =0 (initially) 4=>{2,2} since k >=1 left {2} and coin=1^2=1 now 2=>{1,1} i.e. x=2; now take both coin 2^2=4 so answer = 1+4=5 then why 6 in testcase ...

    1|
    Permalink
  • TejasReedy9
    4 years ago+ 0 comments

    biased for p2 i think

    1|
    Permalink
  • bozhidar_k_ganev
    5 years ago+ 1 comment

    Hi! I am wondering how to pay only 14 coins for tower high 62? According to my calculations the last one that would be possible with 14 coins is 59. Could someone please show me a counterexample of how it is possible? Thank you in advance!

    1|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature