11053 - Flavius Josephus Reloaded

[Adrian Kuegel]

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]

Ok, thanks.

[annhy]

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]

STL set is not the only way to implement a set. Hand-made hashtable would be much faster than it.

[annhy]

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]

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.

[AhmadKhatar]

Hi!
Why TLE for this solution?
Please help!
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;
}

Thanks in advance!

[brianfry713]

memset is going to be slow.
See http://www.informatik.uni-ulm.de/acm/Lo ... judge.html