10750 - Beautiful Points

[rotoZOOM]

Hi !

Could you give me some tricks to find two points with shortest distance between them. O(N^2) algo is too slow for N=10000.

THanks in advance

[Krzysztof Duleba]

My O(n^2) got AC in 4.5s, so O(n^2) isn't too slow. Algo for O(n log n) is a bit complex, you can read about it in CRL. The main idea is to divide and conquer.

[rotoZOOM]

My O(n^2) got AC in 4.5s, so O(n^2) isn't too slow. Algo for O(n log n) is a bit complex, you can read about it in CRL. The main idea is to divide and conquer.

Did your algo got AC in online contest ?
Mine not.
What does CRL means ?

THanks

[sohel]

My algo is also O(nlogn) but I didn't use divide and conquer to solve this problem.

- I sort all the points with respect to the x-coordinate and then wrt y-coordinate incase of a tie.... and this takes O(nlogn) time.

- then I search for the closest pair points using approx. O(n).

My code gets AC in 0.166 seconds and it is ranked 1st ( as at today).
http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10750

What does CRL means ?

Isn't it the algo book by Coreman.

[rotoZOOM]

My algo is also O(nlogn) but I didn't use divide and conquer to solve this problem.

- I sort all the points with respect to the x-coordinate and then wrt y-coordinate incase of a tie.... and this takes O(nlogn) time.

- then I search for the closest pair points using approx. O(n).

My code gets AC in 0.166 seconds and it is ranked 1st ( as at today).
http://acm.uva.es/cgi-bin/OnlineJudge?ProblemStat:10750

Can you explain in more detail your second point.
I thought about sorting, but I didn't understand what to do in further. )

[sohel]

Can you explain in more detail your second point.
I thought about sorting, but I didn't understand what to do in further. )

Here it goes:
For each point P, check all the points from P[i-1] to its left until the distance of P->P[j] is more than dist of P->p[j+1].

Although it might look to be a n^2 algo but invariably the second loop terminates early.

[rotoZOOM]

Can you explain in more detail your second point.
I thought about sorting, but I didn't understand what to do in further. )

Here it goes:
For each point P, check all the points from P[i-1] to its left until the distance of P->P[j] is more than dist of P->p[j+1].

Although it might look to be a n^2 algo but invariably the second loop terminates early.

Probably I don't understand exactly what you mean.
But for this example what you code output:
4 points (x,y):

A: (0,0)
B: (1,100)
C: (2,50)
D: (3,0)

As I understand sort isn't change any points place.
Well when we go from the last D point we check it with C point,
then we break as dist(D,B)>dist(D,C), and we never check (D,A), but
(D,A) is the shortest distance.

May be I didn't understand something ?

[Krzysztof Duleba]

What does CRL means

The book by Cormen, Rivest, Leiserson. A must-read.

For each point P, check all the points from P[i-1] to its left until the distance of P->P[j] is more than dist of P->p[j+1].

Although it might look to be a n^2 algo but invariably the second loop terminates early

Not only this is worst-case O(n^2) , I believe it is also incorrect. Either you haven't told us about some important trick that saves the day, or OJ test cases are hopeless.

BTW: guys, how did you make it to quote with "Krzysztof Duleba wrote:" instead of "Quote:"?

[rotoZOOM]

What does CRL means

The book by Cormen, Rivest, Leiserson. A must-read.

For each point P, check all the points from P[i-1] to its left until the distance of P->P[j] is more than dist of P->p[j+1].

Although it might look to be a n^2 algo but invariably the second loop terminates early

Not only this is worst-case O(n^2) , I believe it is also incorrect. Either you haven't told us about some important trick that saves the day, or OJ test cases are hopeless.

BTW: guys, how did you make it to quote with "Krzysztof Duleba wrote:" instead of "Quote:"?

Just press "Reply with quote" button located in upper-right corner of message ))))
I hope I can get this book as electronic book.

[sohel]

Believe it or not... the method I used got AC.
.. and my program was completly wrong.

My program produces the wrong output for the case rootZOOM mentioned.

Here goes the correct algo: ( hopefully )

sort all the points wrt x first then y.

then for each point P check all the points to its left until the difference between P.x and P[j].x is more then the current minimum value found.

where j = i-1, i-2, ..... , 0.

Warning : This case might not work for data to the limit.

[Per]

Yeah, that's the standard O(n^2) algo, so that should give TLE if the test data is constructed carefully enough.

[Arm.Turbo]

Believe it or not... the method I used got AC.
.. and my program was completly wrong.

My program produces the wrong output for the case rootZOOM mentioned.

Here goes the correct algo: ( hopefully )

sort all the points wrt x first then y.

then for each point P check all the points to its left until the difference between P.x and P[j].x is more then the current minimum value found.

where j = i-1, i-2, ..... , 0.

Warning : This case might not work for data to the limit.

I use the same algo but get in result 2 second run time. How I can speed up it in ten times??

[rotoZOOM]

Believe it or not... the method I used got AC.
.. and my program was completly wrong.

My program produces the wrong output for the case rootZOOM mentioned.

Here goes the correct algo: ( hopefully )

sort all the points wrt x first then y.

then for each point P check all the points to its left until the difference between P.x and P[j].x is more then the current minimum value found.

where j = i-1, i-2, ..... , 0.

Warning : This case might not work for data to the limit.

I use the same algo but get in result 2 second run time. How I can speed up it in ten times??

If you used algo explained by sohel last time then you can't speed up your
run time, cause your method have complexity O(N^2) see Per reply.

[sohel]

The reason behind my code being very fast is that I have used the wrong algorithm and that takes O(NlogN) time.

I mean I have used this one:

For each point P, check all the points from P[i-1] to its left until the distance of P->P[j] is more than dist of P->p[j+1].

I have no idea how it worked and why the judge data is very shallow.

[rotoZOOM]

The reason behind my code being very fast is that I have used the wrong algorithm and that takes O(NlogN) time.

I mean I have used this one:

For each point P, check all the points from P[i-1] to its left until the distance of P->P[j] is more than dist of P->p[j+1].

I have no idea how it worked and why the judge data is very shallow.

If you use that kind of algo and you got AC, then judge data is incomplete.