11762  Race to 1
Moderator: Board moderators
11762  Race to 1
What's the problem of my code I m getting WA again & again.
To solve this I follow this:
1. Generate prime upto 1000000.
2. Get this primes in a sequence in another array.
3. Just follow instruction & check divisibility & calculate required turns D to be 1.
Can any one help me why I m getting WA.
To solve this I follow this:
1. Generate prime upto 1000000.
2. Get this primes in a sequence in another array.
3. Just follow instruction & check divisibility & calculate required turns D to be 1.
Can any one help me why I m getting WA.
Re: 11770(Race to 1)WA
I do following process:
1. Store all prime numbers upto n
2. Divide d with a prime number and count it untill d become 1
3. continue divide operation withe next prime if d!=1 ( Untill prime <= d )
4. Print the counter value.
I get WA.
Can anyone help please?
1. Store all prime numbers upto n
2. Divide d with a prime number and count it untill d become 1
3. continue divide operation withe next prime if d!=1 ( Untill prime <= d )
4. Print the counter value.
I get WA.
Can anyone help please?

 New poster
 Posts: 32
 Joined: Sat Dec 29, 2007 9:08 pm
 Location: CSEDU , Dhaka
 Contact:
Re: 11770(Race to 1)WA
If I am not wrong, you are not calculating expected value.
suppose n = 10,
so primes smaller than 10 are 2,3,5,7
so probability of choosing one of these number to divide 10 is 1 / 4.
so E(10) = 1/4 ( E(10) (10 is not divisible by 7) + E(10 / 5 ) + E(10) + E(10 / 2) ) + 1
suppose n = 10,
so primes smaller than 10 are 2,3,5,7
so probability of choosing one of these number to divide 10 is 1 / 4.
so E(10) = 1/4 ( E(10) (10 is not divisible by 7) + E(10 / 5 ) + E(10) + E(10 / 2) ) + 1
A learner......

 New poster
 Posts: 32
 Joined: Sat Dec 29, 2007 9:08 pm
 Location: CSEDU , Dhaka
 Contact:
Re: 11770(Race to 1)WA
You have 4 primes in hand 2 , 3 , 5 , 7 and you are to divide 10 by one of them,
but you don't know by which one, you have to choose one of them randomly, if you fail to get the correct one,
you have wasted one move and you will choose another one randomly.
If you choose 2, then number of moves will be f(5) + 1 [ f(n) = number of moves to make n 1. and + 1 bcz you are making a move]
But if you choose 3, you can not divide 10 by 3 , so you have to start from 10 again, and number of moves will be f(10) + 1
for 5 and 7 ...........
But probability of choosing anyone number from these 4 numbers is 1 / 4 .
So expected number of moves will be f(10) = 1 / 4 [ f(5) + 1 + f(10)+ 1 + f(2)+ 1 + f(10) + 1]
= 1 / 4 [ f(5) + f(10) + f(2) + f(10) ] + 1
but you don't know by which one, you have to choose one of them randomly, if you fail to get the correct one,
you have wasted one move and you will choose another one randomly.
If you choose 2, then number of moves will be f(5) + 1 [ f(n) = number of moves to make n 1. and + 1 bcz you are making a move]
But if you choose 3, you can not divide 10 by 3 , so you have to start from 10 again, and number of moves will be f(10) + 1
for 5 and 7 ...........
But probability of choosing anyone number from these 4 numbers is 1 / 4 .
So expected number of moves will be f(10) = 1 / 4 [ f(5) + 1 + f(10)+ 1 + f(2)+ 1 + f(10) + 1]
= 1 / 4 [ f(5) + f(10) + f(2) + f(10) ] + 1
A learner......

 Learning poster
 Posts: 64
 Joined: Fri Sep 25, 2009 11:29 am
 Location: Chittagong,University of chittagong
 Contact:
11762  Race to 1
I don't understand the problem and answer .
Can any body help me?
Can any body help me?
Try to catch fish rather than asking for some fishes.

 Learning poster
 Posts: 64
 Joined: Fri Sep 25, 2009 11:29 am
 Location: Chittagong,University of chittagong
 Contact:
Re: 11770(Race to 1)WA
Can You Explain this For
n=13
n=13
Try to catch fish rather than asking for some fishes.
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Re: 11762  Race to 1
What is "this"?And he calls this D.
I don't understand the difference between N and D in the problem statement. The author describes a process to get D to 1 and then asks how long it will take for N to get to 1, but there is nothing in the problem statement that describes how N changes. I'm confused.
If only I had as much free time as I did in college...
Re: 11762  Race to 1
Hmm, looks like it is indeed a bit confusing.
this means N. The author was trying to say that initially D is equal to N and in each subsequent operation D will get reduced to some smaller number.
We are interested in how long it takes for D to reach 1. So you can actually ignore N altogether in this problem and assume that the input given is actually D.
I will inform the author to make the statement less ambiguous. Thanks for spotting it.
this means N. The author was trying to say that initially D is equal to N and in each subsequent operation D will get reduced to some smaller number.
We are interested in how long it takes for D to reach 1. So you can actually ignore N altogether in this problem and assume that the input given is actually D.
I will inform the author to make the statement less ambiguous. Thanks for spotting it.