|
|
back to boardHow to solve it in O(n^2) without gcd? 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)? Re: How to solve it in O(n^2) without gcd? 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. Re: How to solve it in O(n^2) without gcd? Posted by shad 26 Sep 2011 11:02 But function (dx,dy,dz) -> abs(dx) + 5*(abs(dy) + 5*dz)
is not biection Re: How to solve it in O(n^2) without gcd? Posted by OZone 1 Apr 2013 15:34 I didn't get it. Could you explain more? |
|
|
