How to avoid TL?

Posted by

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?

Posted by

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?

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.

Posted by

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?

Posted by

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?

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.