Блог пользователя niti94

Codesprint Elemination Round 2 Problem
Автор niti94, 10 лет назад, По-английски

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

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
10 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    10 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить