|
|
вернуться в форумПоказать все сообщения Спрятать все сообщения O(N log N) is possible. Of course, but not in 0.062 s. :) 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 ;) 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 my email: onlyforme_@ok.kz My mail is hulakov@gmail.com 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:09can anybody explain me n ^ 3/2 algo? I have solved it using Binary Search Tree |
|
|