centinelprime420's blog

By centinelprime420, history, 6 weeks ago, In English

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

Tags dfs
 
 
 
 
  • Vote: I like it
  • +5
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by centinelprime420 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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 to node-1. If the value in the neighbour is node or node-1 then 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:

Example

After doing the math I saw that the answer given is wrong in the text given.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yep, it seems that the text given does not present the correct solution to the stated problem.