I am struggling from past week on this question, any suggestion or hint will be appreciated.
I have tree with n nodes with some stones tied on it. I want to make difference between any two adjacent node's stones as 1 or 0. I can do this adding any number of stones any number of times on any node in any order.
Idea is to minimize number of stones needed.
Image Illustration https://drive.google.com/file/d/1zR6e31Ob6Fr_LX1LbepbPUifirmGbJTk/view?usp=sharing
First, notice that you cannot remove stones. For that reason you cannot lower the maximum number of stones on any node. You would have to do something involving the node with max stones first, then the node with second to max and so on. Let's keep a heap/priority_queue with the biggest value at the top. Then consider a lee/bfs algorithm, but always take the source as the biggest value node. When moving to the neighbours you can change their values on the graph by adding at most
node-1-neighbour. That gets you tonode-1. If the value in the neighbour isnodeornode-1then don't change that. When you change the value in the graph you will also need to update the key in the heap/p_q. The complexity should be O(NlogN) where N is the number of nodes.The example you gave would go like:
heap: {(4, 6), (5, 5), (2, 4), (3, 2), (1, 1)}
node=4, stones=6, heap: {(5, 5), (2, 4), (3, 2), (1, 1)}
Update node (2, 4) to (2, 5), add=1
heap: {(5, 5), (2, 5), (3, 2), (1, 1)}
node=5, stones=5, heap: {(2, 5), (3, 2), (1, 1)}
Update node (3, 2) to (3, 4), add=3
heap: {(2, 5), (3, 4), (1, 1)}
node=2, stones=5, heap: {(3, 4), (1, 1)}
Do not update node (3, 4). Update node (1, 1) to (1, 4), add=6
heap: {(3, 4), (1, 4)}
node=3, stones=4, heap: {(1, 4)}
No neighbour, no update
node=1, stones=4
heap: {}
After doing the math I saw that the answer given is wrong in the text given.
Yep, it seems that the text given does not present the correct solution to the stated problem.