Stone Piles Discussions | Algorithms | HackerRank

Sort by

recency

|

24 Discussions

|

  • + 0 comments
    MAXN = 53
    
    G = [-1] * MAXN
    dp = [[-1 for _ in range(15)] for _ in range(MAXN)]
    vis = [[False for _ in range(100000)] for _ in range(MAXN)]
    
    def grundy(pile_size):
        if G[pile_size] != -1:
            return G[pile_size]
        backTrack(pile_size, pile_size)
        
        ret = 0
        while vis[pile_size][ret]:
            ret += 1
        G[pile_size] = ret
        return ret
    
    def getCount(s, k):
        if k == 0:
            return int(s == 0)
        if dp[s][k] != -1:
            return dp[s][k]
        
        ret = 0
        for i in range(1, s // k + 1):
            ret += getCount(s - k * i, k - 1)
        
        dp[s][k] = ret
        return ret
    
    def backTrack(init_pile_size, curr_pile_size, prev=0, xr=0):
        if curr_pile_size == 0:
            if prev:
                vis[init_pile_size][xr] = True
            return
        
        st = prev + 1
        for i in range(st, min(curr_pile_size, init_pile_size - 1) + 1):
            backTrack(init_pile_size, curr_pile_size - i, i, xr ^ grundy(i))
    
    def main():
        import sys
        input = sys.stdin.read
        data = input().split()
        
        t = int(data[0])
        index = 1
        
        for _ in range(t):
            n = int(data[index])
            index += 1
            xr = 0
            
            for _ in range(1, n + 1):
                v = int(data[index])
                index += 1
                xr ^= grundy(v)
            
            if xr:
                print("ALICE")
            else:
                print("BOB")
    
    if __name__ == "__main__":
        main()
    
  • + 0 comments

    thnmks for share

  • + 0 comments

    A strong sentence is the cornerstone of an engaging piece of writing writing. Be prepared with a tool that makes it easier to weave entire text : , which will make your narratives flow more naturally. No more speculating; just clarity and involvement in each phrase.

  • + 0 comments

    Grundy numbers for 0:0,1:0,2:0,3:1,4:0,5:2,6:3,7:4,8:0 Grundy number for n>=9 = n-4

    Using Grundy Numbers following code:

    def stonePiles(arr): maps = {0:0,1:0,2:0,3:1,4:0,5:2,6:3,7:4,8:0} res = 0 for ele in arr: if ele<=8: res^=maps[ele] else: res^=(ele-4) if res == 0: return 'BOB' else: return 'ALICE'

  • + 6 comments

    Hi, I find the blog informative, though... nice work... do share such information. I’ll bookmark your website. Our website nirogayurved is an Ayurved-related website and on our website, you will get all information related to piles and the cure of ayurvedic medicine for piles Problem.