### matavanga's blog

By matavanga, 8 years ago, ,

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.

• 0

 8 years ago, # |   +7 If you want to stick to this approach, just replace Dijkstra with BFS.
•  8 years ago, # ^ |   +1 i tried but that also gives TLE .thanks
•  8 years ago, # ^ |   0 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, # |   +4 plz use pastebin.com to post ur code
•  8 years ago, # ^ |   +1 thanks i shall do it future.
 8 years ago, # |   +1 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, # |   +1 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, # ^ |   +1 can u please explain it a little bit farther?
•  8 years ago, # ^ |   0 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, # ^ |   0 i tried in that way in my code. But am getting TLE.
•  8 years ago, # ^ | ← Rev. 3 →   0 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 >.Here N ≤ 104. It is small value. If you optimise your code, I think you will get AC.
•  8 years ago, # ^ |   0 thanks. got AC after removing the arr[][] variable
 » 5 years ago, # | ← Rev. 2 →   0 try it and solve your problem you can do and take help from specialist ..............................
 » 5 years ago, # |   0 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 →   0 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 →   0 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, # ^ |   +11 Your approach will yield a wrong answer on the following case:1---2---3---4In 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, # ^ |   0 @Akul — Thanks for pointing out the bug. But, as you said, the Logic is yet to be verified.
•  » » » » 5 years ago, # ^ |   0 Why don't you just find the diameter of the tree??
•  » » » » » 5 years ago, # ^ |   0 @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, # |   0 how to find the longest path using dfs?
•  » » 5 months ago, # ^ |   0 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, # |   -10