11053 - Flavius Josephus Reloaded

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

11053 - Flavius Josephus Reloaded

Post by shanto86 » Mon Jul 24, 2006 3:02 am

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!

sidky
New poster
Posts: 50
Joined: Wed Nov 06, 2002 1:37 pm
Location: Planet Earth, Universe
Contact:

Post by sidky » Mon Jul 24, 2006 5:22 am

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.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jul 24, 2006 7:02 am

sidky vi, will u tell me ur method a bit ? or can u please send me ur code by PM?
Self judging is the best judging!

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

Post by Adrian Kuegel » Mon Jul 24, 2006 10:50 am

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 .

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jul 24, 2006 3:24 pm

Thank you!
Self judging is the best judging!

farzane
New poster
Posts: 26
Joined: Thu Jun 15, 2006 9:26 am

Post by farzane » Mon Jul 24, 2006 7:14 pm

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

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jul 24, 2006 7:27 pm

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. 
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.
Self judging is the best judging!

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

Post by Adrian Kuegel » Mon Jul 24, 2006 7:58 pm

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.
Last edited by Adrian Kuegel on Mon Jul 24, 2006 9:55 pm, edited 1 time in total.

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Mon Jul 24, 2006 8:41 pm

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

a(ax^2+b)+b mod n formula?
Self judging is the best judging!

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

Post by Adrian Kuegel » Mon Jul 24, 2006 9:54 pm

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

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Tue Jul 25, 2006 3:04 am

Ya i meant that.

Ok thanks.
Self judging is the best judging!

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue Jul 25, 2006 10:39 am

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 ?

User avatar
Krzysztof Duleba
Guru
Posts: 584
Joined: Thu Jun 19, 2003 3:48 am
Location: Sanok, Poland
Contact:

Post by Krzysztof Duleba » Tue Jul 25, 2006 10:44 am

You get *a* period, not necessarily the least one.
For millions of years, mankind lived just like the animals. Then something happened which unleashed the power of our imagination. We learned to talk and we learned to listen...

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue Jul 25, 2006 10:51 am

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

rotoZOOM
Learning poster
Posts: 63
Joined: Mon Dec 22, 2003 5:05 am
Location: Russia, Chelyabinsk
Contact:

Post by rotoZOOM » Tue Jul 25, 2006 10:52 am

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.

Post Reply

Return to “Volume 110 (11000-11099)”