From Wikipedia:
Given n coupons, how many coupons do you expect you need to draw with replacement before having drawn each coupon at least once?
This is a simple and interesting probabilistic problem that you can find in CodeChef.
We’ll solve this problem using the following CodeChef scenario:
There are N songs in the album. In the very beginning, a random song is chosen (here and further “random song” means that every song has equal probability to be chosen). After some song is over the next one is chosen randomly and independently of what have been played before.
Nikita G., being the only one who is not going to drop out from the university, wonders, what is the expected number of songs guys have to listen to until every song is played at least once.
So, we have N songs in the album and we need to get how many songs we need to listen until all of the songs are played, having the songs, the same probability to get chosen to be played. We also need to notice that the songs are not taken away, they remain there to be chosen again.
So, getting into the solution of the problem.
We need to know how many times we have to play songs until we get one different, and we have to do this same procedure until we get to play all of them.
We can think that each song played is going to be a trial into getting a new one and we need to know the expected ammount of trials we’ll need to do to get a success, or a new song. Luckly we have the gemoetric distribution that deals with this kind of models.
The geometric distribution takes only one parameter a it’s the probability of beeing sucessfull in the trial, that is, the probability of getting a new song of the ones we have.
To think better about which is the probability we’ll be having, lets use some examples:
- For the first time we play a song, we could get any of the N songs we have, N / N = 1 (which songs we could play / how many songs we have) will be our probability and the times we’ll be needing to play songs before we get a new one.
- For the second time, we’ll have a probability of N - 1 / N, as one song has been already played.
- For the third time, we’ll have a probability N - 2 / N. And we can see that this gets repeated each time.
We’ll call Pi = N - i / N the probability of getting a new song. Each i:[0, N-1] will refer to each new attempt to get a new song having already played i songs.
Now, we’ll put the geometric distribution to work:
The expectation of the geometric distribution is the expected trials before we get the new song played. This expectation can be written as: E(GD(Pi)) = 1 / Pi.
Using the same examples as before:
- For the first time, we know it’s 1.
- For the second time, we have that the expected amount of trials will be 1 / (N - 1 / N) = N / N - 1.
- For the third time, following the same logic, we’ll have N / N - 2.
So, we know how many trials we need to do before getting each new song, we have left just to sum all the expected trials for each i and we’ll have the amount of times we’ll need to play songs before we get all of them.
The code:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17#include <stdio.h>
unsigned t, n;
double songs;
int main() {
scanf("%d\n", &t);
for (; t > 0; --t) {
scanf("%d\n", &n);
songs = 0;
for (int i = 1; i <= n; ++i) {
songs += (double) n/i;
}
printf("%.1f\n", songs);
}
return 0;
}