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

Maximum Points After Collecting Coins From All Nodes

Number: 3179

Difficulty: Hard

Paid? No

Companies: DE Shaw

Problem Description

Given a tree with n nodes (rooted at node 0), where each node i holds coins[i] coins, you must “collect” coins in an order respecting the parent–child relationship. When collecting coins at a node, you may use one of two strategies:

  1. Option1: Collect coins from the node and gain (effective_coins – k) points.
  2. Option2: Collect coins from the node and gain floor(effective_coins / 2) points, but then all coins in its subtree get reduced by half (i.e. coin values become floor(original/2) for that subtree). Note that if an ancestor used Option2, then the coins at its descendant are already reduced (and multiple Option2’s compound by repeated halving). The goal is to decide for each node which option to use in order to maximize the total points after collecting from every node.

Key Insights

  • The tree is traversed from the root respecting parent–child order.
  • At each node, the coins available depend on how many times Option2 (halving) has been applied on the path from the root.
  • Define a “decay” factor (or count d) such that the effective coins at node i are floor(coins[i] / (2^d)).
  • At every node there are two decisions:
    • Option1: Earn (current_effective_coins – k) and proceed with the same decay d.
    • Option2: Earn floor(current_effective_coins/2) and increase the decay (d+1) for all descendants.
  • Use DFS with memoization (DP) over the tree using the state (node, decay_count). The decay count does not need to be unbounded since coin values quickly drop to zero.
  • Since the tree is undirected (but rooted), avoid revisiting the parent in DFS.

Space and Time Complexity

Time Complexity: O(n * M) where M is the maximum decay depth considered (typically around 15–20, since coins[i] ≤ 10^4). Space Complexity: O(n * M) for the memoization table and recursion stack.

Solution

We use DFS with a state (node, d) representing the maximum points obtainable from that subtree when the coins at the current node have already been decayed d times (i.e. effective value = floor(coins[node] / 2^d)). At every node, we have two choices:

  • If we use Option1, we collect (effective - k) points and the decay remains the same for the children.
  • If we use Option2, we collect floor(effective/2) points and the decay increases by 1 for the children. We recursively compute the accumulated points from all subtrees and take the maximum of these two choices. Memoization helps to avoid recomputation of states in overlapping subproblems.

Code Solutions

# Python solution with DFS and memoization.
import sys
sys.setrecursionlimit(300000)

def maxPoints(edges, coins, k):
    from collections import defaultdict
    n = len(coins)
    tree = defaultdict(list)
    # Build the adjacency list for the tree.
    for u, v in edges:
        tree[u].append(v)
        tree[v].append(u)
    
    # Use a memoization dictionary: key = (node, decay_count)
    memo = {}
    # Limit the decay count to a reasonable maximum; because coins decrease fast.
    MAX_DECAY = 20

    def dfs(node, parent, decay):
        # Use memoized result if available.
        if (node, decay) in memo:
            return memo[(node, decay)]
        
        # Effective coin value after current decays.
        effective = coins[node] >> decay  # coin // (2**decay)
        
        total_children_same = 0
        total_children_more = 0
        # Process all children (avoid going back to parent).
        for child in tree[node]:
            if child == parent:
                continue
            # Option when children use same decay.
            total_children_same += dfs(child, node, decay)
            # Option when children are affected by an extra halving.
            # Ensure decay does not exceed MAX_DECAY.
            new_decay = decay + 1 if decay + 1 <= MAX_DECAY else MAX_DECAY
            total_children_more += dfs(child, node, new_decay)
            
        # Option 1: Do not apply further halving.
        option1 = (effective - k) + total_children_same
        # Option 2: Apply halving at current node and propagate an additional decay.
        option2 = (effective >> 1) + total_children_more
        
        best = max(option1, option2)
        memo[(node, decay)] = best
        return best

    # Start DFS at root with decay=0.
    return dfs(0, -1, 0)

# Example usage:
if __name__ == '__main__':
    edges = [[0,1],[1,2],[2,3]]
    coins = [10,10,3,3]
    k = 5
    print(maxPoints(edges, coins, k))  # Expected output: 11
← Back to All Questions