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

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
Yes. This method is just used to get one element of the cycle. After that, to determine the cycle length you iterate once through the cycle until you will be there again. I didn't explicitly write this into the editorial because I thought it is obvious that this has to be done.

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

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan
Adrian Kuegel wrote: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 .
The second approach is not workable.
Another possibility is to store the numbers of the soldiers in a set and when we calculate a number which is already in the set, we have found the first soldier to commit suicide.
I use the STL set and I have highly optimized my code, but it is still TLE...

If the first soldier dies after about n = 10^6 steps, then n log n = 3*10^7.
It is not workable for too many such cases.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
STL set is not the only way to implement a set. Hand-made hashtable would be much faster than it.

annhy
New poster
Posts: 40
Joined: Sun May 27, 2007 1:42 am
Location: Taiwan
Thanks, mf.

I know that there are still many ways to implements a set.
I even take a read on the O(log log n)-query-time van Emde Boas tree.

But I am so lazy such that I always wish to use the wheel that others have made.

And finally I give up to use sets.
I use Pollard Rho algorithm and get AC.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:
I even take a read on the O(log log n)-query-time van Emde Boas tree.
A good hashtable is faster than that -- O(1), on average.

New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

### Re: 11053 - Flavius Josephus Reloaded

Hi!
Why TLE for this solution?
1000000 iteration of the main loop is not time-consuming!
Here is the code:

Code: Select all

``````#include <iostream>
#include <cstring>
#include <map>

using namespace std;

long long int n, a, b;
char seen [ 1000000000 ];
int ind [ 1000000 ];
int rem;

void process();

int main()
{
cin >> n;
while ( n != 0 )
{
cin >> a >> b;
process();
cin >> n;
}

return 0;
}

void process()
{
memset( seen, 0, sizeof(seen) );
long long int next = 0;
int cnt = 0 ;

while ( true )
{
if ( seen[ next ] == 0 )
{
seen[ next ] = 1;
ind[ cnt++ ] = next;
}
else
{
for ( int i = 0; i < cnt; i++ )
{
if ( ind[ i ] == next )
{
rem = n - (cnt - i);
break;
}
}

break;
}
next = (((a * ((next * next) % n)) % n) + b) % n;
}

cout << rem << endl;
}``````