You are right! a. I set T(C,C)=0 so that P(C,n) does not depend on P(C,n-1), otherwise you are correct that the sum does not converge. b. Typo! It should read as you pointed out.
I was trying to prove that my solution is equivalent to the solution in the editorial, but it seemed quite hard and I abandoned it. I made up a formal model for the problem that reads like that: - Let states s[0],s[1],...s[n-1] (in our problem s[0] means 0 unique cards, etc). - Let transitions between states with probabilities p[i,j] (in our problem p[i,j]=T[i,j], with one exception p[C,C]=0 because after reaching s[C] we do not want to move anymore) - Now the question is what is the expected number of steps to move from s[0] to s[C] on the above defined graph? --~--~---------~--~----~------------~-------~--~----~ 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 -~----------~----~----~----~------~----~------~--~---
