vatsal's blog

How to solve Hotels from POI?
By vatsal, history, 8 years ago, In English

How to solve this problem from POI? It simply states: Given a tree find a triplet of nodes (a,b,c) such that distance between each other is same!

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

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

That's not what the problem is asking. It asks to compute the number of such triplets.

You can prove that for any such triplet, there must exist another vertex L which is between them in the tree (i.e., L-A, L-B, L-C forms a star-like shape), and the distances L-A, L-B, L-C must be equal. So you loop over every vertex L, then run DFS counting vertices at each distance. Gives O(n^2) runtime.

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

    Won't that overcount? Like in the sample itself, the distance of nodes {4, 6, 7} are all 2 from the node 2, so we count them once, but then the nodes {4, 6, 7} are also at distance 1 from the node 5 and so we count them again. How do we account for this?

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

      Right. You should only count triples which are in different branches of the tree going out of L. (Note that there may be Ω(n) of these branches, so you need to do that in a non-slow way.)

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

Check out this

→ Reply