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

Daniel TLE [10] // Задача 1491. Нереальная история 14 окт 2006 15:37

TLE №18
Can you please give me any hint?

Victor Barinov (TNU) Re: TLE // Задача 1491. Нереальная история 14 окт 2006 16:52

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

Ostap Korkuna (LNU) Re: TLE [7] // Задача 1491. Нереальная история 15 окт 2006 01:40

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

Victor Barinov (TNU) Re: TLE // Задача 1491. Нереальная история 15 окт 2006 02:42

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

Yosif Yosifov Re: TLE // Задача 1491. Нереальная история 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 .. )

HASK Re: TLE [4] // Задача 1491. Нереальная история 15 окт 2006 19:52

I got a AC, thx.

Begemot Re: TLE [3] // Задача 1491. Нереальная история 16 окт 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] // Задача 1491. Нереальная история 16 окт 2006 20:07

Daniel Re: O(N) solution is very simple. Just two loops! (-) // Задача 1491. Нереальная история 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 :)

sniper Re: O(N) solution is very simple. Just two loops! (-) // Задача 1491. Нереальная история 9 фев 2007 11:40

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

poor English...

KIRILL(ArcSTU) Re: TLE // Задача 1491. Нереальная история 16 окт 2006 22:23

Edited by author 17.10.2006 02:22

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