I took another approach into solving this problem.
1. Let function P(x,n) that gives the probability of having exactly x
unique cards after exactly n purchases.
2. We know that P(0,0) = 1 and P(x != 0,0) = 0.
3. We know that P(x,n) = Sum[P(i,n-1)*T(i,x),{i,0,x}], where T(x,y) is
as described in the contest's analysis: "Let's call T(x,y) the
probability of ending up with y different cards after opening a new
pack [and having initially x unique cards]." In other words the
probability of having x cards after n purchases depends on the sum of
probabilities of having i cards after n-1 purchases times the
probability of going from i unique cards to x unique cards with 1
purchase.
4. With the above recursive equation we can compute P(C,n) for every
n.
5. Now the answer to our problem is the expected value of P(C,n), that
is Sum[P(C,n),{n,0,Infinity}].
6. We can compute this series until it stops changing.This may be not as clean and slick as the solution in the analysis, but it still works. --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
