wretched's blog

By wretched, history, 6 weeks ago, In English

I can findout the farthest nodes of a tree using dfs or bfs.How can I solve this problem using these technique or anything is new to solve this problem? Problem link : https://lightoj.com/problem/visiting-islands Help plz.

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

»
6 weeks ago, # |
Rev. 6   Vote: I like it +3 Vote: I do not like it

Since, the graph may contain many trees. Find the diameter $$$d_i$$$ and order $$$o_i$$$ of each tree and pair them up {$$$d_i, o_i$$$} and sort them in decreasing diameter and order.

And answer each query, if $$$k > max(o_i)$$$ then it's impossible and if $$$k \leq d_0$$$ then it's $$$k - 1$$$ else iterate through the pairs till $$$k \leq o_i$$$, then it's $$$d_i - 1 + 2(k - d_i)$$$.

P.S. Precalculate the answers till $$$max(o_i)$$$ since the last condition might TLE.

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

    What is order here?

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

      Number of vertices in a graph.

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

        ""else iterate through the pairs till k≤oi, then it's di−1+2(oi−k)."" This portion is not clear to me.Please make me clear. Thanks for your co-operation.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Oops! That's a blunder. I changed it to $$$d_i - 1 + 2(k - d_i)$$$ now since you have to pay $$$2(k - d_i)$$$ to visit $$$k - d_i$$$ islands before you visit the farthest node.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
            Rev. 2   Vote: I like it 0 Vote: I do not like it

            What's the logic also behind this :( Again this portion is not clear.

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

              It'll be more clear if you draw a tree with nodes hanging from its diameter.

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

                Thank you.

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

                  Ping me after you implement it. I'm not sure if this works, I didn't even try to implement it.

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

            Got it :)