OJ Board

How to solve it? I can understand that we have to get the first number in the sequence thta will come twice, then compute the loop length. But how?

i solved it by using a hash table. but it took 4 seconds. the time limit in the contest was 3 seconds. i am also eager to know how to solve it under 3 seconds.

sidky vi, will u tell me ur method a bit ? or can u please send me ur code by PM?

sidky wrote:i am also eager to know how to solve it under 3 seconds.

The description of the solutions for the problems are now online.
You can read them at http://www.informatik.uni-ulm.de/acm/Lo ... judge.html .

Thank you!

Is there any other link like the one you introduce above describing about other problems in this site ?(for example for last contests)

What is this method? can any one explain me with example please?

@farzane, if the contest is something special, then sometimes explanations r available over net. to get that u need to google with the contest name.

Lets take the second sample input (5 1 1)
The soldier numbers calculated are:
0, 1, 2, 0, 1, 2, ...

Now both pointers start at 0
One pointer always skips a number, the other takes every number.
pointer 1 | pointer 2 | step
2 | 1 | 1
1 | 2 | 2
0 | 0 | 3

So after 3 steps they both point to number 0
Since the first pointer took a bigger distance than the second pointer, it means it already went through the cycle at least once, so number 0 must be part of the cycle.

that means, for double jumping pointer, u will make:

a(ax^2+b)+b mod n formula?

I guess you meant
a(ax^2+b)^2+b mod n

Actually it is easier to implement the formula in a function, e.g., named "next".
Then one pointer advances with p1 = next(p1), the other with p2 = next(next(p2))

Ya i meant that.

Ok thanks.

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 some ?

You get *a* period, not necessarily the least one.

Additionally, you've got your table wrong at T=4. It should be

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.