11762 - Race to 1

All about problems in Volume 117. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

11762 - Race to 1

Post by Mehadi » Sun Jan 24, 2010 11:30 am

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

Post by nazmuldiu » Sun Jan 24, 2010 12:36 pm

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?

shiplu_1320
New poster
Posts: 32
Joined: Sat Dec 29, 2007 9:08 pm
Location: CSEDU , Dhaka
Contact:

Re: 11770-(Race to 1)WA

Post by shiplu_1320 » Sun Jan 24, 2010 5:23 pm

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

Post by nymo » Sun Jan 24, 2010 8:24 pm

@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

Post by shiplu_1320 » Sun Jan 24, 2010 8:44 pm

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

Post by nymo » Sun Jan 24, 2010 9:16 pm

@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

Post by arifcsecu » Sat Feb 20, 2010 1:15 pm

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

Post by arifcsecu » Sat Feb 20, 2010 2:06 pm

Can You Explain this For
n=13
Try to catch fish rather than asking for some fishes.

User avatar
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

Post by Abednego » Mon Jan 30, 2012 10:01 am

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

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

Re: 11762 - Race to 1

Post by sohel » Mon Jan 30, 2012 10:29 pm

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.

User avatar
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

Post by Abednego » Mon Jan 30, 2012 11:03 pm

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

Post Reply

Return to “Volume 117 (11700-11799)”