\n
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.
\nCan 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.
\n","author":{"@type":"Person","name":"Utsav Patel"},"upvoteCount":2,"answerCount":4,"acceptedAnswer":null}}Reputation: 35
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]
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
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
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:
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
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
Reputation: 8773
Here is what you could do:
Upvotes: 2