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

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

Post by Adrian Kuegel » Tue Jul 25, 2006 4:18 pm

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:

Post by rotoZOOM » Tue Jul 25, 2006 5:55 pm

Ok, thanks.

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

Post by annhy » Tue Jul 03, 2007 3:03 am

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:

Post by mf » Tue Jul 03, 2007 5:05 am

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

Post by annhy » Tue Jul 03, 2007 5:22 am

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. :wink:

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:

Post by mf » Tue Jul 03, 2007 6:11 am

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
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 11053 - Flavius Josephus Reloaded

Post by AhmadKhatar » Sun Mar 24, 2013 12:18 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11053 - Flavius Josephus Reloaded

Post by brianfry713 » Sun Mar 24, 2013 10:52 am

Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 110 (11000-11099)”