minimario's blog

Extending 700B: Connecting Universities
By minimario, history, 8 years ago, In English

I was looking back on some previous contests, and I got to this problem.

I know the algorithm, which can be found on editorial: check each edge, and add min of subtree sizes when this edge is broken. But how do we extend this to find the pairs that we want to match? This algorithm gives the distance, not the pairs to be matched, and the editorial claims "not many modifications required".

However, I can't see it. If anyone could help, I would be really appreciated!

Thanks,

minimario

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

Comments Comments (8)
| Write comment?
»
8 years ago, # |
  Vote: I like it +17 Vote: I do not like it

I have a different solution, which allows you to find one optimal matching.

The algorithm is based on a greedy approach: Suppose that the root of the tree is some node s. Then trying to make pairs of node in such a way that the paths must pass through the root seems to be better than connecting nodes in a same subtree.

We need so select a root so that all connected paths contain the root. This matching strategy is only possible when no subtree contains more than half of important nodes. (Important node is a node needs to be paired.)

Thanks to the Centroid decomposition algorithm, we know that such a root always exists. Amazingly, since every path of paired nodes pass through the root, the distance between them equals to sum of distance from each node to the root. Which means, the total distance of all pairs is always same as the total distance from all important nodes to root, no matter how we connect them.

Hence, in order to find the maximum value of total pairwise distances, we only need to find a centroid and calculate the distance from it to all the nodes.

In the extension of finding an adequate matching, you can simulate the greedy approach. Don't hesitate to ask me further in details.

→ Reply
»
8 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I have another approach.
take the euler tour of the tree. sort the vertices by the starting time. now match the ith vertex with i+k th vertex.
somehow this works, though i don't know the proof.

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

I see that this extension has already been answered. I have another extension that I had thought of. Can this problem be solved if the edges of the tree are weighted?

Note that the method sorting vertices by dfs time does not work here. I know we can solve it if weight is O(1) (say  ≤ 10) by simply creating duplicate nodes and solving in O(c·n)(where c ≤ 10). However, if someone knows of a better solution, please comment. :)

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

    I think that the same thing as the editorial will work here. For each edge, add w * min(a, b), where a and b are the size of the components when we remove the edge.

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

      Can you prove/explain why?

      I cant seem to find this completely intuitive. Also, what would the method to recover matching after this calculation?

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

        Hi, I could not understand why you can't find the same argument intuitive . The same argument works because choosing the nodes in that way includes the edges which could have been included by choosing the vertices from same subtree along with a few more edges. So this solution is guaranteed to be correct. I hope you understand my argument. Indeed our solution for the previous case was also hinged on the same idea

        → Reply