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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Maximum Points After Collecting Coins From All Nodes

Difficulty: Hard

Problem Description

There exists an undirected tree rooted at node 0 with n nodes labeled from 0 to n - 1. You are given a 2D integer array edges of length n - 1, where edges[i] = [a_i, b_i] indicates that there is an edge between nodes a_i and b_i in the tree. You are also given a 0-indexed array coins of size n where coins[i] indicates the number of coins in the vertex i, and an integer k.

Starting from the root, you have to collect all the coins such that the coins at a node can only be collected if the coins of its ancestors have been already collected.

Coins at node i can be collected in one of the following ways:

  • Collect all the coins, but you will get coins[i] - k points. If coins[i] - k is negative then you will lose abs(coins[i] - k) points.
  • Collect all the coins, but you will get floor(coins[i] / 2) points. If this way is used, then for all the node j present in the subtree of node i, coins[j] will get reduced to floor(coins[j] / 2).

Return the maximum points you can get after collecting the coins from all the tree nodes.

Key Insights

  • The tree structure allows for a depth-first search (DFS) approach to traverse and collect coins.
  • Each node has two options for coin collection, leading to decisions that affect downstream nodes.
  • The goal is to maximize points collected while adhering to the constraints of collecting coins in specific orders.
  • Using memoization can optimize the exploration of possible choices at each node.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the tree, as we need to visit each node once. Space Complexity: O(n), for storing the adjacency list of the tree and the recursion stack during DFS.

Solution

To solve the problem, we will use a depth-first search (DFS) approach to traverse the tree. We will represent the tree using an adjacency list and recursively calculate the maximum points for each node. At each node, we will decide whether to collect coins in the first way or the second way, and we will track the total points collected.

  1. Build an adjacency list from the edges array to represent the tree.
  2. Implement a DFS function that takes the current node, its parent (to avoid traversing back), and calculates the points.
  3. For each node, compute the points based on the two options for coin collection and return the maximum points possible.

Code Solutions

def maxPoints(edges, coins, k):
    from collections import defaultdict
    
    # Construct the adjacency list for the tree
    tree = defaultdict(list)
    for a, b in edges:
        tree[a].append(b)
        tree[b].append(a)
    
    def dfs(node, parent):
        total_points = 0
        subtree_points = 0
        can_collect = False
        
        for neighbor in tree[node]:
            if neighbor != parent:
                child_points = dfs(neighbor, node)
                if child_points > 0:
                    can_collect = True
                subtree_points += child_points
        
        # Calculate points for current node
        collect_first = coins[node] - k
        if collect_first < 0:
            collect_first = -collect_first
        
        collect_second = coins[node] // 2
        
        # If we can collect from the subtree, we take the best option
        if can_collect:
            total_points = max(collect_first + subtree_points, collect_second + subtree_points)
        else:
            total_points = collect_first
        
        return total_points
    
    return dfs(0, -1)
← Back to All Questions