Link to problem statement on HackerRank
We are given a tree than some of it's nodes has a machine on it, we have to cut the some edges so that no two of them have a path to each other. The cost of the edges we cut must be minimized.
First Approach : Disjoint Set
What happened in my mind : I looked at the final state, how does it look? We have a forest and each tree in this forest has exactly one node with a machine in it. (You can prove that each tree in this forest has exactly one tree, not zero, by proof of contradiction) Some edges have been cut in order to help us get to this state, right? The total cost of these edges must be minimized. This was when I thought of disjoint-set data structure. As you see we have some sets that no two of them have common nodes. (This is also like a maximum spanning tree, that from some point if two end-points of an edge have a machine in their component we will not do that) So we sort the edges in decreasing order to their cost and start merging them, when two endpoints of an edge have a machine in their component we skip that and add that to the answer.
The proof that this gives us the optimum answer is most like the proof that Kruskal algorithm gives Minimum Spanning Tree.
For more details look at my code on github.
Second Approach : DP on Tree
When I see a tree it's always tempting to hang it from some node and make it a rooted tree :D then compute something for the subtree starting from each node. In this case after some thinking I decided to define this value for each node f(node, machineCount, parent) means we have a rooted tree with node being the root of it, we want to do what the problem has asked for the subtree starting from node (cutting some edges in the subtree starting from node, so that no two machine nodes have a path to each other) and after paying that cost, if we grab node and take it, the component connected to it has exactly machineCount number of machines in it. Here machineCount can be 0 or 1, meaning the component connected to node must have exactly 0 or exactly 1 machines.
According to my experience in these questions (dp on tree), defining what needs to be returned is the key point. (exactly 0 or 1 machines in this case, and what 0 or 1 machine means?)
Now let's check different situations when calculating f(node, machineCount)
The very base case here is when machineCount = 0 and node has a machine in it, the answer to this would be Infinity, because we can't remove that machine, and whatever we cut from the subtree of node, when we grab node, it has at least 1 machines in it.
Now let's calculate this value
zeroMachineCost : (no machine in the subtree of tree)
zeroMachineCost = SUM ( min ( f(child, 0), f(child, 1) + edge(node, child) ) ) for all children of node
We have calculated the cost for when the component connecting to node has zero machines in it.
if ( machineCount == 1 && hasMachine[node] == true ) return zeroMachineCost;
if( machineCount == 0 && hasMachine[node] == false ) return zeroMachineCost;
The only case that remains is when hasMachine[node] is false, and machineCount == 1,
which means we need to take one machine from one of subtrees of node.
This part calculates that, as you see we assume the answer is Infinity (because node may has no children), then one by one for each child we deduct the part that had been added to zeroSum previously and add a component with one machine starting at child.
Take a look at my code on github for more details.
We are given a tree than some of it's nodes has a machine on it, we have to cut the some edges so that no two of them have a path to each other. The cost of the edges we cut must be minimized.
First Approach : Disjoint Set
What happened in my mind : I looked at the final state, how does it look? We have a forest and each tree in this forest has exactly one node with a machine in it. (You can prove that each tree in this forest has exactly one tree, not zero, by proof of contradiction) Some edges have been cut in order to help us get to this state, right? The total cost of these edges must be minimized. This was when I thought of disjoint-set data structure. As you see we have some sets that no two of them have common nodes. (This is also like a maximum spanning tree, that from some point if two end-points of an edge have a machine in their component we will not do that) So we sort the edges in decreasing order to their cost and start merging them, when two endpoints of an edge have a machine in their component we skip that and add that to the answer.
The proof that this gives us the optimum answer is most like the proof that Kruskal algorithm gives Minimum Spanning Tree.
For more details look at my code on github.
Second Approach : DP on Tree
When I see a tree it's always tempting to hang it from some node and make it a rooted tree :D then compute something for the subtree starting from each node. In this case after some thinking I decided to define this value for each node f(node, machineCount, parent) means we have a rooted tree with node being the root of it, we want to do what the problem has asked for the subtree starting from node (cutting some edges in the subtree starting from node, so that no two machine nodes have a path to each other) and after paying that cost, if we grab node and take it, the component connected to it has exactly machineCount number of machines in it. Here machineCount can be 0 or 1, meaning the component connected to node must have exactly 0 or exactly 1 machines.
According to my experience in these questions (dp on tree), defining what needs to be returned is the key point. (exactly 0 or 1 machines in this case, and what 0 or 1 machine means?)
Now let's check different situations when calculating f(node, machineCount)
The very base case here is when machineCount = 0 and node has a machine in it, the answer to this would be Infinity, because we can't remove that machine, and whatever we cut from the subtree of node, when we grab node, it has at least 1 machines in it.
Now let's calculate this value
zeroMachineCost : (no machine in the subtree of tree)
zeroMachineCost = SUM ( min ( f(child, 0), f(child, 1) + edge(node, child) ) ) for all children of node
We have calculated the cost for when the component connecting to node has zero machines in it.
if ( machineCount == 1 && hasMachine[node] == true ) return zeroMachineCost;
if( machineCount == 0 && hasMachine[node] == false ) return zeroMachineCost;
The only case that remains is when hasMachine[node] is false, and machineCount == 1,
which means we need to take one machine from one of subtrees of node.
This part calculates that, as you see we assume the answer is Infinity (because node may has no children), then one by one for each child we deduct the part that had been added to zeroSum previously and add a component with one machine starting at child.
Take a look at my code on github for more details.
No comments:
Post a Comment