Discussion @ 1491. Unreal Story @ Timus Online Judge

TLE

Posted by Daniel 14 Oct 2006 15:37

TLE №18
Can you please give me any hint?

Re: TLE

Posted by Victor Barinov (TNU) 14 Oct 2006 16:52

Try to find algo O(n^(3/2)) or O(n log n )

Re: TLE

Posted by Ostap Korkuna (LNU) 15 Oct 2006 01:40

The best solution is O(n). Try to find it.

Re: TLE

Posted by Victor Barinov (TNU) 15 Oct 2006 02:42

O(n) ???? Are your sure???
Strange that fastest solution works in 0.125 seconds...

Re: TLE

Posted by Yosif Yosifov 15 Oct 2006 18:24

O(N) is without using any kind of tree , right ? Can I get a hint to this solution? ( I have already solved the problem .. )

Re: TLE

Posted by HASK 15 Oct 2006 19:52

I got a AC, thx.

Re: TLE

Posted by Begemot 16 Oct 2006 17:30

Please, advice me how to solve this problem? Using binary tree? Thank you.

O(N) solution is very simple. Just two loops! (-)

Posted by Vladimir Yakovlev (USU) 16 Oct 2006 20:07

Re: O(N) solution is very simple. Just two loops! (-)

Posted by Daniel 16 Oct 2006 20:32

I have found this O(N) solution! Just 1 minute thinking.
It is really very easy.
Thank you very much. If I didnt know that there is such solution I would hardly find it :)

Re: TLE

Posted by KIRILL(ArcSTU) 16 Oct 2006 22:23

Edited by author 17.10.2006 02:22

Re: O(N) solution is very simple. Just two loops! (-)

Posted by sniper 9 Feb 2007 11:40

From left and from right(Because b>=a).
That's the two loops?!

poor English...

Discussion of Problem 1491. Unreal Story