Discussion @ 1521. War Games 2 @ Timus Online Judge

O(n ^ 3/2) in 0.062 s. :)

Posted by Walrus 20 Dec 2006 00:10

Re: O(n ^ 3/2) in 0.062 s. :)

Posted by CHN_XT 20 Dec 2006 12:18

O(N log N) is possible.

Re: O(n ^ 3/2) in 0.062 s. :)

Posted by Walrus 20 Dec 2006 16:06

CHN_XT wrote 20 December 2006 12:18

O(N log N) is possible.

Of course, but not in 0.062 s. :)

Re: O(n ^ 3/2) in 0.062 s. :)

Posted by CHN_XT 21 Dec 2006 16:59

Yes.

Re: O(n ^ 3/2) in 0.062 s. :)

Posted by Burunduk1 21 Dec 2006 20:57

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 ;)

Re: O(n ^ 3/2) in 0.062 s. :)

Posted by Walrus 21 Dec 2006 21:12

Burunduk1 wrote 21 December 2006 20:57

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

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

Re: O(n ^ 3/2) in 0.062 s. :)

Posted by Burunduk1 21 Dec 2006 21:31

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

Sent...

Posted by Walrus 21 Dec 2006 21:53

Resources for Informatics Olympiad

Posted by Ngô Minh Đức 24 Dec 2006 15:39

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

Re: Resources for Informatics Olympiad

Posted by Vedernikoff Sergey 26 Dec 2006 12:52

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

No subject

Posted by Peter Ivanov 15 Jan 2007 07:19

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

Re: No subject

Posted by KIRILL(ArcSTU) 15 Jan 2007 14:18

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

Re: No subject

Posted by Peter Ivanov 17 Jan 2007 02:36

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

Re: No subject

Posted by KIRILL(ArcSTU) 17 Jan 2007 03:03

Check your mail

can anybody give me O(n^3/2) solution?

Posted by Arthur 17 Mar 2007 08:07

my email: onlyforme_@ok.kz

Re: O(n ^ 3/2) in 0.062 s. :)

Posted by Giorgi Saghinadze (Tbilisi SU) 24 Jul 2007 16:13

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

Can anybody give me O(n^3/2) solution?

Posted by nightwalker 13 Jun 2008 02:15

My mail is hulakov@gmail.com

Re: No subject

Posted by Oleg Strekalovsky [Vologda SPU] 21 Jul 2010 18:08

Peter Ivanov wrote 15 January 2007 07:19

Vedernikoff Sergey: I don't know what your algo is but mine has O(NlogN) like most of the others.

Edited by author 15.01.2007 07:20

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

Re: No subject

Posted by Artem Khizha [DNU] 1 Nov 2010 23:24

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

Discussion of Problem 1521. War Games 2