Discussion @ 1422. Fireflies @ Timus Online Judge

Victor Barinov (TNU) How to solve it in O(n^2) without gcd? [3] // Problem 1422. Fireflies 2 Jun 2008 02:53

Hi!
I am trying to solve this problem with hashing, but my method use gcd so the complexity is O(n^2 log n).
What hash-function i must use for hashing vector (vx,vy,vz)?

Denis Koshman Re: How to solve it in O(n^2) without gcd? [2] // Problem 1422. Fireflies 23 Aug 2008 19:51

I used the following:
abs(dx) + 5*(abs(dy) + 5*dz)
dz >= 0 always, for dz=0 dy>=0 always, for dz=0 and dy=0 dx>=0 always

It is base-5 representation of |dx|, |dy|, |dz|. 5 is a good multiplier because it may turn into LEA EAX, [EAX*4+EAX] in assembler which is pretty fast.

I still had TL18 when I ran main loops for 1..n x 1..n. Then I changed algo to run for 1..n x i+1..n, and got AC in 1.7 sec. No floats or int64.

shad Re: How to solve it in O(n^2) without gcd? // Problem 1422. Fireflies 26 Sep 2011 11:02

But function (dx,dy,dz) -> abs(dx) + 5*(abs(dy) + 5*dz)
is not biection

OZone Re: How to solve it in O(n^2) without gcd? // Problem 1422. Fireflies 1 Apr 2013 15:34

I didn't get it. Could you explain more?

Discussion of Problem 1422. Fireflies