OJ Board

Krzysztof Duleba wrote: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 wrote: What does CRL means ?

sohel wrote: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

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

sohel wrote:

rotoZOOM wrote: 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.

What does CRL means

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

Krzysztof Duleba wrote:

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 wrote: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.

Arm.Turbo wrote:

sohel wrote: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??

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].

sohel wrote: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.