## 11762 - Race to 1

Moderator: Board moderators

New poster
Posts: 18
Joined: Sun Jan 24, 2010 11:17 am

### 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.

nazmuldiu
New poster
Posts: 4
Joined: Wed Aug 05, 2009 6:05 pm

### 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.

shiplu_1320
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
A learner......

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### Re: 11770-(Race to 1)WA

@shiplu:

Can you elaborate? Thanks in advance.
regards,
nymo

shiplu_1320
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
A learner......

nymo
Experienced poster
Posts: 149
Joined: Sun Jun 01, 2003 8:58 am
Location: :)

### Re: 11770-(Race to 1)WA

@Shiplu: Thanks very much.
regards,
nymo

arifcsecu
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?
Try to catch fish rather than asking for some fishes.

arifcsecu
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
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

And he calls this D.
What is "this"?

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

sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

### 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.

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

Thanks, Sohel.
If only I had as much free time as I did in college...