Utsav Patel
Utsav Patel

Reputation: 35

Decrement Node Values to 0 of a given tree

This is similar to a practice question I am trying to solve. You have been given an undirected tree with an array of values. A value val[i] is associated with the ith node. In a single operation, two nodes can be selected, and their values can be decremented by 1 at a cost equal to the distance between the two nodes, i.e., the number of edges in the simple path between them. It is possible to select the same node for the operation and decrease its value by 2 at the cost of 0.

t_from = [1, 1, 3, 5], t_to = [2, 3, 4, 5] val = [3, 2, 4, 2, 5]

enter image description here

The optimal strategy is to choose nodes (1, 1), (2, 2), (3, 3), (3, 3), (4,4), (5,5) and (5,5) again to get the costs [1, 0, 0, 0, 1]. Now the nodes (1,5) can be chosen to decrease by 1 at the cost of 2. So the final answer would be 2.

Can anyone tell me what can I do? I used bfs to find the pairs of odd-weighed nodes and added the distance between them but it does not work.

Upvotes: 2

Views: 5509

Answers (4)

Carry Anderson
Carry Anderson

Reputation: 1

Actually, the minimum cost is equivalent to the length of the pathway consisting of all nodes with odd values. Now, this optimization problem looks more concrete and determined.

It is easy to carry out this calculation, when a tree structure is given. Then, we just need to push all the vertices along the pathway. It can be recursively solved as below:

vector<int> res;
void findOddNode(TreeNode* root, vector<int> path){
    if (root == nullptr) {
        path.clear();
        return;
    }
    path.push_back(root->val);
    if (root->val % 2){
        res.insert(end(res), begin(path), end(path));
        path.clear();
    }
    findOddNode(root->left, path);
    findOddNode(root->right, path);
}

Then, the answer would be res.size() - 1.

Upvotes: 0

Toh Kai Feng
Toh Kai Feng

Reputation: 11

Credit to @maraca for the approach!

counting the steps from the leaves essentially makes this algorithm a modified topological BFS.

Rough steps are that:

  1. remove leaves that are even (or "0" after mod 2)
  2. if leaf is odd -> totalcost += 1
  3. if leaf is odd, invert parent (1 -> 0, or 0 -> 1)
  4. check whether parent is a leaf
def getMinCost(val, t_nodes, t_from, t_to):
    
    for i in range(len(val)):
        val[i] = val[i]%2
    adj_list = [set() for i in range(t_nodes)]
    for i in range(len(t_from)):
        adj_list[t_from[i]-1].add(t_to[i]-1)
        adj_list[t_to[i]-1].add(t_from[i]-1)
    
    leaves = [i for i in range(t_nodes) if len(adj_list[i]) == 1]
    
    remaining = t_nodes 
    cost = 0 
    while leaves and remaining > 2:
        remaining -= len(leaves) 
        newLeaves = []
        for leaf in leaves:
            #each leaf only has one parent so pop() any from adj_list
            parent = adj_list[leaf].pop() 
            #remove leaf from parent to check if parent becomes a leaf
            adj_list[parent].remove(leaf) 
            if val[leaf] == 1: #odd
                cost += 1
                # parnt shd change fm 0 to 1 and vice versa
                val[parent] = 1 - val[parent]
                
            if len(adj_list[parent]) == 1:
                newLeaves.append(parent)
                
        leaves = newLeaves
    
    # check if remaining two leaves are odd
    if leaves and val[leaves[0]] == 1:
        cost += 1
        
    return cost

Upvotes: 1

Haoyue Zhang
Haoyue Zhang

Reputation: 1

This is Problem 3 in my practice section ...

Key: It's a tree rather than a graph !!!

just take it as Linked List problems in LeetCode, solve it from leaf to root.

Upvotes: -1

maraca
maraca

Reputation: 8773

Here is what you could do:

  1. Set all node values to modulo 2, so you have only 1s and 0s.
  2. Create a hash map where you have the node as key and the distance travelled as value.
  3. Add all nodes with a value of 1 which are at the deepest level to the map with a distance travelled of 0.
  4. Add all nodes with a value of 1 which are 1 level above the current one to a new hash map with a distance travelled of 0.
  5. For all entries in the old map add the node's parent to the new hash map and increase the distance travelled by one. Whenever there is a collision (a node is already in the hash map) remove the node in the map instead of adding the colliding one and add the distances travelled of both colliding nodes + 1 to the total costs (unless you increase distance travelled before checking collision, then you don't need to do +1).
  6. Repeat steps 4. and 5. until all 1s are consumed. This has to be latest at the root node if the number of nodes with a value of 1 is even, otherwise there is no solution. Total costs should now be the solution. Like this no node is travelling farther than it needs to (well not exactly, there could be a closer node, but then another node would have to travel the same distance more than what we would save).

Upvotes: 2

Related Questions