OJ Board

Ok, thanks.

As I understand, after I find situation: pointers are at one position, I need start to count and wait for second occurency such event.
This will truly period of a cycle.

What will be if the set has a long tail ?
For example,

1 2 3 4 5 6 7 5 6 7 5 6 7 5 6 7 .... and so on

When we use Rho method it'll get incorrect result.
F - first pointer
S - second one
T - step number
F | S | T
2 3 1
3 5 2
4 7 3
5 5 4

So we have cycle of length 4 ....
may be I don't understand ...

Try this example:

There are no negative integers in input. For all calculation I used long double and got AC.

ardiankp Yes, you're right. It is my missing. Now I got AC.
Thank you !

I handled both of this case.
May be I didn't understand description of problem clearly.
Let me present part of my code:

int mas[52][52];
int n,m;

void dropball (int x);

void checkit (int y,int x)
{
if (y+2>=m || (mas[y+2][x-1] && mas[y+2][x+1]))return;
mas[y][x]=0;
if (!mas[y+2][x-1] && !mas ...

Hi !

Are there exists some tricky cases ?
I think my program works fine, but it got WA everytime.

If upper bound will be 10000 and amount of numbers is 10000 than
N*B = 10^8. If we use bit sieve of Erathosphenes it take us 12,5 Mb and
complexity O(10^8*log(10^8)). What do you think about it ?

I used a (hopefully) correct implementation of the O(n log n) divide-and-conquer algorithm, got AC in the contest.

As Krzysztof said, you can read about it in CLR. Or it shouldn't be too hard to find a page describing it, if you search for closest pair.
Yeah, thanks.
I tried to find CLR but its ...

If you use that kind of algo and you got AC, then judge data is incomplete.
Don't be so surprised. Big cases are often random generated, so one can achieve good time making some assumptions that usually, but not always, hold.
What about correct algo ?
Does every people (who got AC in online ...

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

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

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

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