10015  Joseph's Cousin
Moderator: Board moderators
10015  Joseph's Cousin
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
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

 Experienced poster
 Posts: 167
 Joined: Fri Oct 19, 2001 2:00 am
 Location: Saint Petersburg, Russia
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.
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.
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:
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:
Still, it doesn't give a closedform solution, as there's no formula for nth prime.
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 zerobased 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));
}
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);
}

 Experienced poster
 Posts: 106
 Joined: Thu Jan 29, 2004 12:07 pm
 Location: Bangladesh
 Contact:
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.

 Learning poster
 Posts: 63
 Joined: Tue Sep 20, 2005 12:31 am
 Location: Dhaka
 Contact:
10015
I got TLE
And it takes CPU 240.033
But Why?????
Here is my code:
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<n1)
{
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]);
}
}
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.
Ami ekhono shopno dekhi...
HomePage
HomePage

 Learning poster
 Posts: 63
 Joined: Tue Sep 20, 2005 12:31 am
 Location: Dhaka
 Contact:
10015  Joseph's Cousin
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=UL+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[iL]) 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[1L]=false;
if(L<=2) flag[2L]=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<number1)
{
i=prime[num];
i=i%v.size();
k=k+i1;
if(i==0) v.erase(k);
else if(k<v.end()) v.erase(k);
else
{
i=kv.end();
k=v.begin()+i;
v.erase(k);
}
++num;
}
printf("%d\n",*v.begin());
v.empty();
}
return 0;
}
Re: 10015 Joseph's Cousin
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:
From http://www.sgi.com/tech/stl/Vector.html:
And FYI: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.
 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]
10015 Joseph's Cousin
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=UL+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[iL]) 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[1L]=false;
if(L<=2) flag[2L]=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<number1)
{
i=prime[num];
if(i>number) i=i%(numbernum);
k=(k+i1)%(numbernum);
v.erase(v.begin()+k);
++num;
}
printf("%d\n",v[0]);
v.clear();
}
return 0;
}
Re: 10015 Joseph's Cousin
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
I've added assert(0 <= k && k < v.size()); before
and it was triggered because k==1, which happened because at previous step k and i were zeroes, and 1 % whatever == 1.v.erase(v.begin()+k);
10015  Joseph's Cousin
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=UL+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[iL]) 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[1L]=false;
if(L<=2) flag[2L]=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<number1)
{
i=prime[num];
if(i>number) i=i%v.size();
if(i==0 && k==0) k=v.size()1;
else k=(k+i1)%v.size();
v.erase(v.begin()+k);
++num;
}
printf("%d\n",v[0]);
v.clear();
}
return 0;
}
Re: 10015  Joseph's Cousin
I've tried running your program, it prints 3 for every n>=3:
(that's 1, 1, and then 3 repeated 3499 times, in case if you don't know what uniq c does)
You must have been extremely, unbelievably lucky to have typed only those few cases into uva toolkit...
Code: Select all
$ g++ o p p.cc
$ (seq 1 3501; echo 0)  ./p  uniq c
2 1
3499 3
$
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).i check different type of input and output in UVa toolkit and my code and i have correct answer
You must have been extremely, unbelievably lucky to have typed only those few cases into uva toolkit...