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 »

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 »

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 »

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 »

@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 »

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 »

@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 »

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 »

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

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

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

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 »

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

Post Reply

Return to “Volume 117 (11700-11799)”