CODEWITHSUNDEEP
algorithmbinary-treedynamic-programming
flapdoodle
flapdoodle

Reputation: 33

Algorithm to find a set of "k" marked vertices in a binary tree that minimizes distance to marked ancestors for all nodes

This is the original problem I have:

enter image description here

I need to design an algorithm as described above.
I am not sure how to go about this.
I know that the root node should always be marked because otherwise the cost would be infinite.
I think I should probably use dynamic programming somehow.
I am not sure how to break the problem up into sub-problems.

Upvotes: 3

Views: 474

Answers (1)

Saeid
Saeid

Reputation: 4265

Create a dynamic state with three variables as follows

func( index of node(ind),
      how many nodes can be colored in this subtree(k),
      distance to closest marked ancestor(d) )

Now for each state you can calculate the best result like this:

if node is leaf
    if k>0 // if we can mark this node the distance will be 0
        return 0
    return d
result = infinity

// if this node is not marked yet, and we can mark it, mark it
if d != 0 and k > 0 
    result = min(result, func(ind, k-1, 0)
for t=0 to k
    // dedicate t mark nodes to left child and k-t mark nodes to right child
    result = min(result, func(index of left_child, t, d+1) + 
                         func(index of right_child, k-t, d+1) +
                         d )
return result // sum of the distances of this node and its descendants to the closest marked node

Calling 

func(0, // root index
     k,
     infinity)

will give you the best result.

You can save the result of each state in a memoized table to transform this solution to a dynamic approach.

Upvotes: 1

Related Questions