niti94's blog

Codesprint Elemination Round 2 Problem
By niti94, 10 years ago, In English

Problem

The problem is about devising an optimal strategy, to minimize the diameter of a tree by removing at most K leaves.

One of the solution greedily removed one of the end node of the current diameter, If their are several choices then one of the leaf with maximum no. of diameter starting from it,is preferred)

Code

Can anybody explain me why this will always work..?

Thanks

  • Vote: I like it
  • +3
  • Vote: I do not like it

Comments Comments (3)
| Write comment?
»
10 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

This is my code. And I have no rigorous proof of what I did. But on hindsight, you will always remove those vertices that are the extremes of a diameter because removal of any other vertex will not result in a shorter diameter immediately and in an optimal removal sequence, both removals can be interchanged. Also, once that is settled, the order of removing diameter end leaves is quite natural. As I said, no rigorous proof. :P

→ Reply
  • »
    »
    10 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thank you, I agree that by drawing some random test case it is easy to figure this out.During contest time i couldn't figure out the order of removing diameter end leaves and got a partial score of 46/60.

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

      But the intended solution is more elegant and much simpler to code. I felt really bad after I saw that today. :(

      → Reply