11053  Flavius Josephus Reloaded
Moderator: Board moderators
11053  Flavius Josephus Reloaded
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?
Self judging is the best judging!

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
The description of the solutions for the problems are now online.sidky wrote:i am also eager to know how to solve it under 3 seconds.
You can read them at http://www.informatik.uniulm.de/acm/Lo ... judge.html .
Code: Select all
Advance one pointer in steps of two, another pointer in steps of one. When they point to the same soldier, we know that this is one of the soldiers who will commit suicide.
@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.
Self judging is the best judging!

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
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.
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.
Last edited by Adrian Kuegel on Mon Jul 24, 2006 9:55 pm, edited 1 time in total.

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany

 Learning poster
 Posts: 63
 Joined: Mon Dec 22, 2003 5:05 am
 Location: Russia, Chelyabinsk
 Contact:
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 ?
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 ?

 Guru
 Posts: 584
 Joined: Thu Jun 19, 2003 3:48 am
 Location: Sanok, Poland
 Contact:
Additionally, you've got your table wrong at T=4. It should be
Code: Select all
F S T
5 6 4
6 5 5
7 7 6