We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Subtree Removal Game with Fibonacci Tree

Number: 2153

Difficulty: Hard

Paid? Yes

Companies: Sony

Problem Description

Given an integer n, construct a Fibonacci tree using the following rules:

  • order(0) is an empty tree.
  • order(1) is a tree with a single node.
  • order(n) for n ≥ 2 is a tree with a root whose left subtree is order(n - 2) and right subtree is order(n - 1).

Alice and Bob play a game on this tree where they take turns selecting any node and removing that node along with its entire subtree. The player forced to remove the tree's root loses. Return true if Alice wins under optimal play, and false otherwise.

Key Insights

  • The Fibonacci tree is defined recursively; thus, the game can be analyzed recursively.
  • Evaluating winning positions in such removals often involves calculating Grundy numbers (or nim-values) for game states.
  • The nim-value for a composite game is given by the xor (nim-sum) of the nim-values of independent subgames.
  • Base case: order(1) has only the root, so the player making a move immediately loses.
  • Using dynamic programming (memoization) allows efficient recomputation of the Grundy numbers for subtrees.

Space and Time Complexity

Time Complexity: O(n) due to the recursive computation with memoization. Space Complexity: O(n) for the memoization storage.

Solution

We solve the problem by computing the Grundy number for each order of the Fibonacci tree. The Grundy number of order(n) is derived from its left subtree (order(n-2)) and right subtree (order(n-1)) by taking their xor. If the resulting nim-value is non-zero, the current player (Alice, who starts) has a winning strategy. Base cases include:

  • order(0) is assigned a nim-value of 0.
  • order(1) is losing (nim-value 0) since the only move is to remove the root.

With optimal play, if the computed nim-value for order(n) ≠ 0, Alice wins; otherwise, Bob wins. The solution employs recursion with memoization to compute the values efficiently.

Code Solutions

# Python solution with detailed comments

def subtree_removal_game(n: int) -> bool:
    # Dictionary for memoizing computed Grundy numbers for Fibonacci tree orders.
    grundy = {0: 0, 1: 0}  # Base cases: order(0) and order(1) are losing positions.

    def compute_grundy(k: int) -> int:
        # Return precomputed value if available.
        if k in grundy:
            return grundy[k]
        # Recursively compute the nim-value for the left and right subtrees.
        left = compute_grundy(k - 2)
        right = compute_grundy(k - 1)
        # Combine the nim-values via xor to get the current state’s nim-value.
        current = left ^ right
        grundy[k] = current
        return current

    # Compute the Grundy number for order(n).
    nim_value = compute_grundy(n)
    # A non-zero nim-value means the current player (Alice) has a winning strategy.
    return nim_value != 0

# Example usage:
print(subtree_removal_game(3))  # Expected output: True
print(subtree_removal_game(1))  # Expected output: False
← Back to All Questions