ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 1887. Frequent Flyer Card

Hints
Posted by Abid29 16 Sep 2022 23:03
You only have four things to pick from, so you can calculate each step explicitly. This equation follows the notation in the article: T is the time to collect all of the items, and ti be the time to collect the i-th item after i−1 items have been collected.

E(T)=E(t1)+E(t2)+E(t3)+E(t4)=p1−1+p2−1+p3−1+p4−1.
The probability p1 of picking a new one if you have picked none yet is 1.

The probability p2 of picking a new one if you have picked one depends on which one you picked first. Let's call the items A through D and the probabilities of picking each item if they're all in the box pa through pd.

Then p2 would be
pa(pb+pc+pd)+pb(pc+pd+pa)+pc(pd+pa+pb)+pd(pa+pb+pc).
The above expression is the probability of picking a new one given that A had been picked already, plus the probability of picking a new one given that B had been picked already, and so on.

The expression for p3 will have six terms in the sum; one of these will be papb(pc+pd). The expression for p4 will have four terms in the sum (actually, it's the same term four times!)