Discussion @ 1470. UFOs @ Timus Online Judge

TLE

Posted by KIRILL 27 Sep 2006 00:41

my simple algo don't fit
if compute on each step number of UFO wich
belong to sector - its too long (O(n*n))
What's the correct algo for this task?

Re: TLE

Posted by Slobodan 27 Sep 2006 22:05

You should use cumulative tables...

Re: TLE

Posted by Vedernikoff Sergey 30 Sep 2006 01:50

Octtrees also didn't work! Is there quicker data structure?

I've used 3d Fenwick's tree to get AC (-)

Posted by Anton [SUrSU] 30 Sep 2006 09:27

Re: TLE

Posted by CHN_XT 12 Oct 2006 13:52

Tree Array, like Mobile(IOI2001).

Re: TLE

Posted by lijian 9 Jul 2007 10:54

Should call'Binary Indexed Tree'

Help!!!

Posted by Dart MirzMan C++ Edition (Mirzoyan Alexey, Rybinsk SAAT) 29 Oct 2007 18:34

I use cumulative tables... But I get TLE 5 =(

A[i][j][k][d]=Sum[{i*2^d,j*2^d,k*2^d}:{(i+1)*2^d-1,(j+1)*2^d-1,(k+1)*2^d-1}]

I can add the UFO by log(n) time, but the calculation of the total number of UFOs in a sector are too long... =(

For example, if N=128 and x1=1, y1=1, z1=1, x2=126, y2=126, z2=126 - my algo gives O(n^2) time... =(

No subject

Posted by SuperLight 3 Jan 2008 14:16

My AC program is O((log N)^3) time

Re: No subject

Posted by Denis Koshman 6 Aug 2008 04:53

Mine's too (base4 due to ML). 1.47 sec

Fenwick tree - AC 0.5sec on Java.

Posted by Alex Tolstov 13 Mar 2009 02:25

Re: Fenwick tree - AC 0.5sec on Java.

Posted by Vitalii Arbuzov 23 Mar 2011 22:29

Hm...
My solution uses segment tree in plain array as underlying data structure and it runs in O(n log n) but I've got TLE 6.
Probably it's because I've used java and created a lot of objects while processing.
Will try to tune performance to fit in time bound.

Re: Fenwick tree - AC 0.5sec on Java.

Posted by ONU_Antananarivu 17 Jul 2011 11:38

Got the same problem with segment tree and TLE 6, even though I use C++((

Discussion of Problem 1470. UFOs