Page 1 of 1

11762 - Race to 1

Posted: Sun Jan 24, 2010 11:30 am
by Mehadi
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.

Re: 11770-(Race to 1)WA

Posted: Sun Jan 24, 2010 12:36 pm
by nazmuldiu
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?

Re: 11770-(Race to 1)WA

Posted: Sun Jan 24, 2010 5:23 pm
by shiplu_1320
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

Re: 11770-(Race to 1)WA

Posted: Sun Jan 24, 2010 8:24 pm
by nymo
@shiplu:

Can you elaborate? Thanks in advance.

Re: 11770-(Race to 1)WA

Posted: Sun Jan 24, 2010 8:44 pm
by shiplu_1320
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

Re: 11770-(Race to 1)WA

Posted: Sun Jan 24, 2010 9:16 pm
by nymo
@Shiplu: Thanks very much.

11762 - Race to 1

Posted: Sat Feb 20, 2010 1:15 pm
by arifcsecu
I don't understand the problem and answer .
Can any body help me?

Re: 11770-(Race to 1)WA

Posted: Sat Feb 20, 2010 2:06 pm
by arifcsecu
Can You Explain this For
n=13

Re: 11762 - Race to 1

Posted: Mon Jan 30, 2012 10:01 am
by Abednego
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.

Re: 11762 - Race to 1

Posted: Mon Jan 30, 2012 10:29 pm
by sohel
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.

Re: 11762 - Race to 1

Posted: Mon Jan 30, 2012 11:03 pm
by Abednego
Thanks, Sohel.