O(N log N) is possible.

Of course, but not in 0.062 s. :)

Yes.

In this problem the most time-consuming thing is output.
So your 0.062 it is only fast output.

PS: Btw, O(nlogn) - 0.046 sec ;)

Hmm... 0.046 also is not 0.062 :)
But it is fact: my solution is so simple.

More simple than Interval Tree? =)
Anyway you've intersted me. So if you don't mind, please, send your solution to sk1@hotbox.ru

I plan to create a site collecting articles, ebooks, problems, and so on about algorithms.

I've also uploaded my (too small) solutions to Timus problems, containing 1521.

If you have any resources and want to share, please take a minute. It benefits our problem-solving community!

Here is the URL:

Merry Christmas to all !

Regards,
Minh Duc

Edited by moderator 29.12.2006 09:26

How to speed it up? My O(N*logN*logN) solution takes ~0.7 sec. to get AC...

Vedernikoff Sergey: I don't know what your algo is but mine has O(NlogN) like most of the others. I used Index tree (also known as Dynamic Order Statistics or as Burunduk said - Interval tree - this must be the same).
I am interested in the O(N^3/2) solution. Could someone explain it here?

Edited by author 15.01.2007 07:20

Let's  exchange with our progs.
My is O(N^3/2). Just 316Kb memory is needed for it.
Send it on my e-mail or post your

Kiril, my e-mail is cheater_no1@abv.bg

Check your mail

my email: onlyforme_@ok.kz

can anybody explain me  n ^ 3/2  algo? I have solved it using Binary Search Tree

My mail is hulakov@gmail.com

My solution has O(N*logN*LogN).
Main idea - find k-th order statistics in array, where a[i]=1, if i-th soldier was in circle else  a[i]=0
(use binary search and Fenwick tree).
I don't know how to find k-th order statistics only by Fenwick by O(LgN)

Edited by author 21.07.2010 18:09

Oleg Strekalovsky, you _can_ find k-th order statistics in O(logN). You should use binary search for digits, which is described (e.g.) in TC tutorial:
http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees#find