Discussion @ 1145. Rope in the Labyrinth @ Timus Online Judge

How to avoid TL? misha 25 Dec 2002 10:01

I can't imagine, how to solve this problem in 1 second. Please, help!

Re: How to avoid TL? TheBeet 25 May 2004 15:15

Just BFS two times.
First BFS:
>Start from any place
>>Then Find The one which you arrive at last.
Second BFS:
>Start from this place
>>Then the distance you go farthest is the Answer.

Edited by author 29.05.2004 08:49

How large should the queue be? Maigo Akisame (maigoakisame@yahoo.com.cn) 26 Oct 2004 04:44

I set its size to 50000, and got AC with 989K memory. But I suppose it needn't be so large. Who can tell me the upper bound of its size?

Edited by author 26.10.2004 15:37

You can use two queues. Fu Dong 30 May 2005 18:02

I only used 325KB with BFS.

Edited by author 30.05.2005 18:21

Re: How to avoid TL? program 20 Dec 2007 16:55

First BFS:
Start from any place
Then Find The one which you arrive at last.
Second BFS:
Start from this place
Then the distance you go farthest is the Answer.

I don't understand why does it work?
First BFS may result many different place. Or last element of the queue? But wait how about the orders of the direction?

Second BFS
why?

Re: How to avoid TL? Denis Koshman 4 Aug 2008 13:35

I make tree rooted (parent info consumes only 1Mb - I store direction to the parent). Then for each node I find distance to deepest child (+4Mb). Then for each node I find 2nd maximum, the answer is max(max1+max2). It's general algo for any tree, and it worked here at around 0.093 sec.

Discussion of Problem 1145. Rope in the Labyrinth