elementaryGuy's blog

Need help with Codechef Minimum Subtree Cover Problem
By elementaryGuy, history, 4 years ago, In English

Hello CodeForces! I Need help with SUBTRCOV problem.

My thought process until now : 

- The optimal set always consists of 1-degree nodes

  - Initially we start with a single 1-degree node as the subtree cover

  - Now in each step, if the subtree formed by the current subtree cover has less than k nodes, then we select farthest node from the current subree and add it to the cover.

However I can't think of efficient way of finding the farthest node (my approach involves using dfs everytime to find the farthest node which is O(n)) and hence my solution is O(n^2). Any help will be much appreciated. Thanks in advance.

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hint — The end nodes of the diameter will always be present in the optimal answer. After that select leaves greedily.

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

My approach was to DFS to find a diameter node (this is always a node of greatest depth, irrespective of where you start), and then find the opposite diameter node (node of greatest depth from the other diameter node). This gives you the longest possible path such that you need just 2 nodes. From there your idea is correct, so it's just a question of how to implement. My implementation was to use a priority queue of leaf nodes, and a sparse table to check the lowest ancestor of each node already used, so I could update the depths and reinsert them into the PQ if necessary.

This is just one idea. There may well be more efficient solutions, but this was enough to pass.

My submission is here.

→ Reply