Обсуждение @ 1491. Нереальная история @ Timus Online Judge

TLE

Послано Daniel 14 окт 2006 15:37

TLE №18
Can you please give me any hint?

Re: TLE

Послано Victor Barinov (TNU) 14 окт 2006 16:52

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

Re: TLE

Послано Ostap Korkuna (LNU) 15 окт 2006 01:40

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

Re: TLE

Послано Victor Barinov (TNU) 15 окт 2006 02:42

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

Re: TLE

Послано Yosif Yosifov 15 окт 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

Послано HASK 15 окт 2006 19:52

I got a AC, thx.

Re: TLE

Послано Begemot 16 окт 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! (-)

Послано Vladimir Yakovlev (USU) 16 окт 2006 20:07

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

Послано Daniel 16 окт 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

Послано KIRILL(ArcSTU) 16 окт 2006 22:23

Edited by author 17.10.2006 02:22

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

Послано sniper 9 фев 2007 11:40

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

poor English...

Обсуждение задачи 1491. Нереальная история