Discussion @ 1491. Unreal Story @ Timus Online Judge

Daniel TLE [10] // Problem 1491. Unreal Story 14 Oct 2006 15:37

TLE №18
Can you please give me any hint?

Victor Barinov (TNU) Re: TLE // Problem 1491. Unreal Story 14 Oct 2006 16:52

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

Ostap Korkuna (LNU) Re: TLE [7] // Problem 1491. Unreal Story 15 Oct 2006 01:40

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

Victor Barinov (TNU) Re: TLE // Problem 1491. Unreal Story 15 Oct 2006 02:42

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

Yosif Yosifov Re: TLE // Problem 1491. Unreal Story 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 .. )

HASK Re: TLE [4] // Problem 1491. Unreal Story 15 Oct 2006 19:52

I got a AC, thx.

Begemot Re: TLE [3] // Problem 1491. Unreal Story 16 Oct 2006 17:30

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

Vladimir Yakovlev (USU) O(N) solution is very simple. Just two loops! (-) [2] // Problem 1491. Unreal Story 16 Oct 2006 20:07

Daniel Re: O(N) solution is very simple. Just two loops! (-) // Problem 1491. Unreal Story 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 :)

sniper Re: O(N) solution is very simple. Just two loops! (-) // Problem 1491. Unreal Story 9 Feb 2007 11:40

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

poor English...

KIRILL(ArcSTU) Re: TLE // Problem 1491. Unreal Story 16 Oct 2006 22:23

Edited by author 17.10.2006 02:22

Discussion of Problem 1491. Unreal Story