First you solve the bottom equation for f(1): since f(0)=0, then f(1) =1/2 * f(1)+1, and f(1)=2. After that it is easy to get f(2) from the top equation: f(2)=f (1)+1=3.
In general case the number of terms in each sum and probabilities in every term depend on C, N, and k. The idea is the same though: you will need to know probabilities that you will get 0, 1, 2, or more cards that you need when you buy your next pack. The situation when you may not get any new cards is special, because you have to solve an equation for f(k) (like we did with f(1)). On Sep 11, 11:26 pm, qasim zeeshan <[email protected]> wrote: > Thanks! > > But I am still not able to understand that how you got f(1)=2 and f(2)=3? > > > > On Sat, Sep 12, 2009 at 12:39 PM, bas <[email protected]> wrote: > > > Let f(k) be the expected number of packs we need to buy if we still > > don't have k cards (or we have C-k cards). > > To solve the problem we need to find f(C). Note: f(0)=0. > > > In the first example C=2; > > When we buy the first pack, we will get one of the cards we need with > > the probability 1. > > f(2)=1*f(1)+1 > > means that we expect to buy that many packs to get all the cards we > > need. But we still don't know f(1). > > For k=1 we have one card we need, and we need to find the other one. > > When we buy this next pack, we will get the card we already have with > > a probability 1/2 and the card we need with prob 1/2. > > f(1)=1/2*f(1)+1/2*f(0)+1 > > Then: f(1)=2; f(2)=3 > > > On Sep 11, 9:54 pm, qasim zeeshan <[email protected]> wrote: > > > Hi All, > > > First of all congrats to all who made it to next round. > > > > I have seen some codes for Problem C. but didn't understand. Can anyone > > > please explain both example test cases for Problem C. > > > > Thanks > > > > -- > > > Qasim Zeeshan > > -- > Qasim Zeeshan > PUCIT, PU Alumni '04 > Software Engineer > CambridgeDocs Pakistan > A Division of Document Science | EMC USAhttp://qzeeshan.blogspot.com/ --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
