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

Count Ways to Build Rooms in an Ant Colony

Number: 1313

Difficulty: Hard

Paid? No

Companies: Adobe

Problem Description

You are given n rooms (numbered 0 to n-1) and an expansion plan represented by the array prevRoom where prevRoom[i] indicates that room i can be built only after its previous room prevRoom[i] is built; room 0 is already built (prevRoom[0] = -1). All rooms will eventually be reachable from room 0. You are allowed to build one room at a time (provided its predecessor is built) and can only travel between rooms that are already built and directly connected. Determine the number of valid orders in which you can build all the rooms, modulo 10^9 + 7.

Key Insights

  • The dependency structure forms a tree rooted at room 0.
  • The order in which rooms are built corresponds to a topological ordering that respects the tree structure.
  • The problem reduces to counting the number of ways to interleave the build orders of subtrees.
  • Use combinatorics (multinomial coefficients) to determine how many ways to merge orders of independent subtrees.
  • Precomputing factorials and modular inverses facilitates efficient combination calculations.

Space and Time Complexity

Time Complexity: O(n), where n is the number of rooms (each node is processed once and factorials are computed in O(n)). Space Complexity: O(n), due to the recursion stack (tree traversal) and additional arrays for factorials and tree structure.

Solution

We first convert the expansion plan into a tree representation. For each room (node), we perform a DFS to compute two things: the size of the subtree and the number of ways to build the subtree. For a node, the number of ways to interleave the build orders from its children is given by the multinomial coefficient:

total_ways = (factorial(total_children_count) / (product of factorial(each_child_subtree_size))) * (product of ways for each child)

Precompute factorials and inverse factorials modulo 10^9+7 to efficiently calculate combinations. By recursively combining results from child subtrees, we obtain the number of valid build orders for the entire tree.

Code Solutions

MOD = 10**9 + 7

# DFS to compute ways and subtree sizes
def countWays(prevRoom):
    n = len(prevRoom)
    tree = [[] for _ in range(n)]
    
    # Build the tree from the prevRoom array
    for i in range(1, n):
        tree[prevRoom[i]].append(i)
    
    # Precompute factorials and inverse factorials up to n
    fact = [1] * (n + 1)
    inv_fact = [1] * (n + 1)
    for i in range(1, n + 1):
        fact[i] = fact[i-1] * i % MOD
    inv_fact[n] = pow(fact[n], MOD - 2, MOD)  # Fermat's little theorem for modular inverse
    for i in range(n, 0, -1):
        inv_fact[i-1] = inv_fact[i] * i % MOD

    # DFS function returns a tuple (ways, subtree_size)
    def dfs(u):
        ways = 1
        total_children_size = 0
        # Process all children
        for child in tree[u]:
            child_ways, child_size = dfs(child)
            ways = ways * child_ways % MOD         # Multiply ways from the child
            ways = ways * inv_fact[child_size] % MOD # Divide by factorial(child_size) for merging orders
            total_children_size += child_size        # Aggregate sizes of children
        # Multiply by factorial(total size of merged subtrees)
        ways = ways * fact[total_children_size] % MOD
        return ways, total_children_size + 1  # +1 for the current node
    
    result, _ = dfs(0)
    return result

# Example execution
if __name__ == "__main__":
    # Example 1: expected output is 1 (0 -> 1 -> 2)
    print(countWays([-1, 0, 1]))
← Back to All Questions