matavanga's blog

By matavanga, 8 years ago, In English,

i am trying to solve http://www.spoj.pl/problems/PT07Z/  problem.

i first got the most farthest point from root and then got the farthest point from that point
but i am getting TLE. can you please find the appropriate algorithm for this problem .
thanks




GOT AC!!! 
THANKS ALL.
 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

8 years ago, # |
  Vote: I like it +7 Vote: I do not like it
If you want to stick to this approach, just replace Dijkstra with BFS.
  • 8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    i tried but that also gives TLE .
    thanks

    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      Also I'd suggest that you replace "t=Integer.parseInt(lst[ind].get(i).toString());" with something more reasonable. It looks much like "if (booleanVar.toString().length()==4) {...}".
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it
plz use pastebin.com to post ur code
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it
heights for the two largest in the tree, that is, the two leaves below you can find and the result is the sum of both heights
8 years ago, # |
  Vote: I like it +1 Vote: I do not like it
Use just DP, using simple dfs you can calculate the two deepest nodes and returning the depths of his father, so that it can calculate where the maximum path length in one of its ends to the parent of the node.
  • 8 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    can u please explain it a little bit farther?
    • 8 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's name longest path in a tree - diametr. How to find it?!
      We can find it by using DFS/BFS.
      First, let's run bfs from any vertex. After, take the further vertex, and denote it as u.
      Then, run bfs from u, and find the further vertex from it, and denote it as v.
      Diametr is distance between u and v.
      So, complexity is O(V + E)

      • 8 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it
        i tried in that way in my code. But am getting TLE.
        • 8 years ago, # ^ |
          Rev. 3   Vote: I like it 0 Vote: I do not like it

          Look, you used array N * N. It takes a lot of memory and etc.
          I do not use java, but in C++, you can use vector<vector <int> >.
          Here N ≤ 104. It is small value. If you optimise your code, I think you will get AC.

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

try it and solve your problem you can do and take help from specialist ..............................

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hello you are welcome to CODE FORCES Howsoever long the path may be, you can always rely on Long Path Tool. Its sure to sort out your problem.


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

I also have a problem with this task. My code ( http://ideone.com/RhhwIC ) is getting WA, but I can't find a bad test case. I'm doing DFS to compute paths for all neighbours for all nodes (as a root) and for every node I join two biggest results.

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

I have another inefficient approach for solving this problem. The approach would give TLE, but I want to confirm its validity. Please if you could confirm -

START -

1. Make a list of nodes of the Tree storing the "Degree" of each node along with the neighbors of the node. 

2.Initialize Length=0;

3. While there are nodes present in the tree, perform the following
   a. remove the nodes having degree 1. 

   b. if(number of nodes removed >2 ) length+=2 else length+=1

   c. update degree of node and its neighbors

return length

END.

So, here, what I am essentially doing is tapering down the longest path, starting from all the boundary(degree 1) nodes. Is the solution valid?

Thanks in advance !

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Your approach will yield a wrong answer on the following case:

    1---2---3---4

    In the first step you will remove 1 and 4 and update your length to 1. In the next step you will remove 2 and 3 and update length to 2. But as you can clearly see the longest path is from 1 to 4 of length 3.

    Changing your condition to (nodes removed>=2) will also yield a wrong answer in this case. But I think maybe changing your condition to (nodes removed >= 2) and also adding the case that:

    if(nodes left ==2) length++; return length;
    

    might give you the right answer. No guarantees on that though.

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

      @Akul — Thanks for pointing out the bug. But, as you said, the Logic is yet to be verified.

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

        Why don't you just find the diameter of the tree??

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

          @trophies — I have successfully implemented that approach, but I to set in the intuition right, I wanted to think of the other possibilities/approaches. After all, the real learning is when we try to think of alternative and multiple approaches. The purpose was not just to get to the answer.

»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how to find the longest path using dfs?

  • »
    »
    5 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Use two dfs . Firstly choose an arbitrary node a and find the farthest node b from a using dfs. Then find the farthest node c from b using dfs. The distance between b and c will the answer. Link for my code

»
3 years ago, # |
  Vote: I like it -10 Vote: I do not like it