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

Help required in a recent codechef contest problem
Автор bhagirathinayak48, история, 5 лет назад, По-английски

Can you please help me on this, I commented my queryYour text to link here...

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

»
5 лет назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Say we have a tree as given. If we can find the maximum of the tree, it will have no bad neighbors and be a valid answer. Now let's consider their step — take the centroid of the tree and check it. If there is no bad neighbor we are done, but if there is any bad neighbor then we know that the node we selected cannot be a bad neighbor of the node they returned. That means that if we split the tree on the edge between the two, we get a smaller subtree which also must have a (local) maximum. That (local) maximum will be a valid answer.

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

    I understand that far but I want to know why there will always be a local maxima.

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

      There will always be a local maxima because out of the numbers in the tree there must be a single greatest or many tied for greatest. If there are ties then they are = to each other and therefore make no bad edges. All the other nodes are smaller than them. Therefore all of the largest numbers have no bad edges.

      When we split the tree we don't guarantee that the subtree has the same largest elements, only that you can apply the same reasoning to the new tree.

      → Ответить