10015 - Joseph's Cousin

[Subeen]

i don't understand why my prog. got WA.
pls someone check ur output with mines:
input:
3501
3500
3499
3498
3497
3496
3495
3400
3000
5
4
3
2
1
0

corresponding output:
2995
1543
1868
1090
1244
1694
2753
2482
1361
1
4
1
1
1

[Ivan Golubev]

My accepted solution produces this output for your input:
2326
1835
3164
141
1494
2381
2417
2238
1613
1
4
1
1
1

[Subeen]

thanks for output. I got it AC.

[Sedefcho]

Hello,

I also got ACC on this problem.

First I precalculate the first several primes using the Sieve Method.
Actually I precalculate all primes which are smaller than 40 000.
They are about 4200 so this is enough for us for this problem.

Then I simply use simulation technique. And the only optimization
I do is that I cache the results for the input numbers my
program receives ( as we have a small range for
possible input values 1<=N<=3501 ). This way I never simulate
the process for more than once for a given input number N.

But my program is very slow It got a runtime of about 1 min
on the Online Judge Machine. So ... My question is if there's some
direct formula, which we could use. I doubt it as we have to
deal with primes. Then there should be a better method/algorithm
for solving this problem.

How can other people get a runtime of 0.000 sec? Does
that mean they have just precalculated all the answers
for N = 1,2,...3501 and after that they have just hardcoded
these answers in a second program which they have submitted
to the Judge.

Or ... Is there really some nice solution ( algorithm ) which
could decrease the runtime to let's say several
seconds ( 1 sec, 5 secs or even 10 secs would be perfect ).

Obviously using only a simulation technique we get
terrible runtimes.

[mf]

Hi, sedefcho.

I don't know any simple formula for this problem too, and I'd be quite surprised if one exists.
But I can show how to solve the problem without rude simulation:

Code: Select all

/* Returns zero-based position of the survivor among n people, with elimination
   starting from person 0, and step prime[p] */
int survivor(int n, int p)
{
        int m, k;

        if (n <= 1)
                return 0;               /* one person left, he's the only survivor */

        m = (prime[p] - 1) % n;         /* who's leaving now */
        k = survivor(n - 1, p + 1);     /* the final survivor's position, relative to m */

        /*
         *  Now we need to map the final survivor's position back into the old
         *  indexing system. Here's an example for case n=9, m=3:
         *
         *          0 1 2 3 4 5 6 7 8  -- initial indexing
         *                x            -- person m=3 gets eliminated
         *  k=      5 6 7 . 0 1 2 3 4  -- what will be returned by the recursive call
         *  result: 0 1 2 . 4 5 6 7 8  -- back to the old indexing
         */ 

        if (k < (n - m - 1))
                return (k + m + 1);
        else
                return (k - (n - m - 1));
}

My program runs 0.004 sec on the judge. I got 0.000 by sending a precomputed table.

If you get more interested about the Josephus' problem and how a solution like the one above can be derived, take a look at chapter 1 of "Concrete Mathematics" by Graham, Knuth, Patashnik.

edit:
I just tried to rework my solution again. The function survivor() can be simplified to:

Code: Select all

int survivor(int n)
{
	int i, s;

	for (s = 0, i = 1; i <= n; i++)
		s = (s + prime[n - i]) % i;      /* assumes prime[0] = 2, ...*/

	return (s + 1);
}

Still, it doesn't give a closed-form solution, as there's no formula for n-th prime.

[Raiyan Kamal]

I have used array version of linked list. In an array a, for every i, a is the index of the next element. I initialize the array with, a=i+1 for all 1<=i < n AND a[n]=1. Then I run the simulation. I count the steps and when my step count is equal to the current prime, i delete a node from the list. To optimize it a little bit, i look for cycles.

[mohsincsedu]

I got TLE
And it takes CPU 240.033
But Why?????

Here is my code:

Code: Select all

#include<stdio.h>
#include<string.h>
#include<math.h>

#define MAX 3502
#define M 40000

long prime[MAX];
char composite[M];

void seive()//Generate prime number up to 40000
{
	unsigned long i,j,k;
	memset(composite,'0',sizeof(composite));
	composite[1] = '1';

	int end = sqrt(MAX);
	for(i = 3;i<=end;i+=2)
	{
		if(composite[i]=='0')
		{
			k = M/i;
			for(j = i;j<=k;j+=2)
				composite[i*j] = '1';
		}
	}
	prime[0] = 2;
	for(i = 3,j = 1;i<MAX;i+=2)
		if(composite[i]=='0')
			prime[j++] = i;
}

void main()
{
	unsigned long i,j,k,count,n,test,J[MAX];
	char table[MAX];

	seive();
	n = 1;
	while(n<MAX)//for every numner find the last person
	{

		memset(table,'1',n+1);
		count = k = i = test = 0;
		while(count<n-1)
		{

			if(i>=n)
				i = 0;
			if(table[i]=='1')
			{
					test++;
			}
			if(test==prime[k])
			{
				table[i] = '0';
				count++;
				k++;
				test = 0;
			}
			i++;
		}
		for(i = 0;i<n;i++)
			if(table[i]=='1')
				break;
		J[n] = i+1;
		n++;
	}
	while(scanf("%lu",&n)!=EOF)
	{
		if(!n)
			break;
		printf("%lu\n",J[n]);
	}
}

[Jan]

Why you are finding last person for every number. Just read the input and find it. That would be enough to get rid of TLE.

[mohsincsedu]

Hi Jan ..........
Thanks for ur reply.............!!!!!!!

I changed my code.

But This time i got TLE!!!!!

Plz help me!!!

[sayem]

can anyone tell me why runtime error?

Code: Select all

#include<stdio.h>
#include<math.h>
#include<vector>

using namespace std;
int prime[4200];

void sieve(int L,int U) 
	{
	int i,j,d;
	d=U-L+1; 
	bool *flag=new bool[d+1];
	for (i=(L%2!=0);i<d;i+=2) flag[i]=false;
	for (i=3;i<=sqrt(U);i+=2) 
		{
		if(i>L && !flag[i-L]) continue;
		j=L/i*i; 
		if (j<L) j+=i;
		if (j==i) j+=i; 
		for (j-=L;j<d;j+=i) flag[j]=false;
		}
	int n=0;
	if(L<=1) flag[1-L]=false;
	if(L<=2) flag[2-L]=true;
	for (i=0;i<d;i++) 
		{
		if (flag[i]) 
			{
			prime[n]=L+i;
			n++;
			}
		}
	}

int main()
{
sieve(1,33000);
int number;
while(scanf("%d",&number)==1 && number>0 && number<=3501)
	{
	if(number==2) 
		{
		printf("1\n");
		continue;
		}
	vector<int> v;
	int num=0,i;
	for(i=1;i<=number;i++)
		v.push_back(i);
	vector<int>::iterator k;
	k=v.begin();
	while(num<number-1)
		{
		i=prime[num];	
		i=i%v.size();
		k=k+i-1;
		if(i==0) v.erase(k);
		else if(k<v.end()) v.erase(k);
		else 
			{
			i=k-v.end();
			k=v.begin()+i;
			v.erase(k);
			}
		++num;
		}	
		printf("%d\n",*v.begin());
		v.empty();
	}
return 0;
}

[mf]

Your usage of iterators is wrong. After you've issued "v.erase(k);" you can not use iterator k anymore.

From http://www.sgi.com/tech/stl/Vector.html:

A vector's iterators are invalidated when its memory is reallocated. Additionally, inserting or deleting an element in the middle of a vector invalidates all iterators that point to elements following the insertion or deletion point.

And FYI:

• v.empty() only returns a boolean - is the vector is empty or not (i.e. v.size() == 0). It doesn't clear the vector, or alter its contents in any way.
• Instead of *v.begin() you can simply write v[0]

[sayem]

hi mf whats problem now? still run time error

Code: Select all

#include<stdio.h>
#include<math.h>
#include<vector>

using namespace std;
int prime[4200];

void sieve(int L,int U) 
	{
	int i,j,d;
	d=U-L+1; 
	bool *flag=new bool[d+1];
	for (i=(L%2!=0);i<d;i+=2) flag[i]=false;
	for (i=3;i<=sqrt(U);i+=2) 
		{
		if(i>L && !flag[i-L]) continue;
		j=L/i*i; 
		if (j<L) j+=i;
		if (j==i) j+=i; 
		for (j-=L;j<d;j+=i) flag[j]=false;
		}
	int n=0;
	if(L<=1) flag[1-L]=false;
	if(L<=2) flag[2-L]=true;
	for (i=0;i<d;i++) 
		{
		if (flag[i]) 
			{
			prime[n]=L+i;
			n++;
			}
		}
	}

int main()
{
sieve(1,33000);
int number;
vector<unsigned int> v;
while(scanf("%d",&number)==1 && number>0 && number<=3501)
	{
	int num=0,i;
	for(i=1;i<=number;i++)
		v.push_back(i);
	int	k=0;
	while(num<number-1)
		{
		i=prime[num];	
		if(i>number) i=i%(number-num);
		k=(k+i-1)%(number-num);
		v.erase(v.begin()+k);
		++num;
		}	
		printf("%d\n",v[0]);
		v.clear();
	}
return 0;
}

[mf]

What's the problem with you? Can't you use a debugger at all? Or this runtime error doesn't occur in your environment? - in the latter case try to compile and run your program from Ubuntu, it should be very close to what judge is using.

I've added assert(0 <= k && k < v.size()); before

v.erase(v.begin()+k);

and it was triggered because k==-1, which happened because at previous step k and i were zeroes, and -1 % whatever == -1.

[sayem]

can anyone tell for which input it show WA? i check different type of input and output in UVa toolkit and my code and i have correct answer but server show WA what will i do. here is my code>>>>>>

Code: Select all

#include<stdio.h>
#include<math.h>
#include<vector>

using namespace std;
int prime[4200];

void sieve(int L,int U) 
	{
	int i,j,d;
	d=U-L+1; 
	bool *flag=new bool[d+1];
	for (i=(L%2!=0);i<d;i+=2) flag[i]=false;
	for (i=3;i<=sqrt(U);i+=2) 
		{
		if(i>L && !flag[i-L]) continue;
		j=L/i*i; 
		if (j<L) j+=i;
		if (j==i) j+=i; 
		for (j-=L;j<d;j+=i) flag[j]=false;
		}
	int n=0;
	if(L<=1) flag[1-L]=false;
	if(L<=2) flag[2-L]=true;
	for (i=0;i<d;i++) 
		{
		if (flag[i]) 
			{
			prime[n]=L+i;
			n++;
			}
		}
	}

int main()
{
sieve(1,33000);
int number;
vector<int> v;
while(scanf("%d",&number)==1 && number>0 && number<=3501)
	{
	int num=0,i;
	for(i=1;i<=number;i++)
		v.push_back(i);
	int	k=0;
	while(num<number-1)
		{
		i=prime[num];	
		if(i>number) i=i%v.size();
		if(i==0 && k==0) k=v.size()-1;
		else k=(k+i-1)%v.size();
		v.erase(v.begin()+k);
		++num;
		}	
		printf("%d\n",v[0]);
		v.clear();
		}
return 0;
}

[mf]

I've tried running your program, it prints 3 for every n>=3:

Code: Select all

$ g++ -o p p.cc
$ (seq 1 3501; echo 0) | ./p | uniq -c
      2 1
   3499 3
$ 

(that's 1, 1, and then 3 repeated 3499 times, in case if you don't know what uniq -c does)

i check different type of input and output in UVa toolkit and my code and i have correct answer

Your program outputs the correct answer in only 14 cases out of 3501 (i.e. the first two 1's are OK, and then there are 12 cases output for which happens to be 3).

You must have been extremely, unbelievably lucky to have typed only those few cases into uva toolkit...