bhagirathinayak48's blog

Help required in a recent codechef contest problem
By bhagirathinayak48, history, 6 years ago, In English

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

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

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

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.

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

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

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

      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.

      → Reply