Discussion @ 1470. UFOs @ Timus Online Judge

TLE KirillB(Arkhangelsk - PomorSU) 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 Slobodan 27 Sep 2006 22:05

You should use cumulative tables...

Re: TLE Vedernikoff 'Goryinyich' Sergey (HSE: АОП) 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 (-) Anton juver++ Postnikov 30 Sep 2006 09:27

Help!!! mirzman 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 SuperLight 3 Jan 2008 14:16

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

Re: No subject Denis Koshman 6 Aug 2008 04:53

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

Fenwick tree - AC 0.5sec on Java. Alex Tolstov (SPb SPU) 13 Mar 2009 02:25

Re: Fenwick tree - AC 0.5sec on Java. 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. malinovyi_ponchik 17 Jul 2011 11:38

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

Re: TLE LittlePig 12 Oct 2006 13:52

Tree Array, like Mobile(IOI2001).

Re: TLE lijian 9 Jul 2007 10:54

Should call'Binary Indexed Tree'

Discussion of Problem 1470. UFOs