RRPLAYER - Editorial

general
, , ,
1

Practice

Contest

PROBLEM LINK:

Author: Roman Rubanenko

Tester: Tuan Anh

Editorialist: Florin Chirica

DIFFICULTY:

easy-medium

PREREQUISITES:

dynamic programming, basic probability theory

PROBLEM:

We add elements from 1 to n to a list until all n elements appear in the list. Each element can be added with the same probability. What’s the expected number of elements from the list?

QUICK EXPLANATION:

Let’s keep dp[i][j] = what’s probability to have j different elements in the list, such as length of the list is i. We can simulate this solution until the probabilities become small enough. Then, we can either notice the pattern or precalculate the answers in a constant vector.

EXPLANATION:

Small values of n

Approach for small values of n is pretty common in probability tasks. Let’s keep dp[i][j] = the probability to have j different elements in the list, such as length of the list is i.

Definition of expected value is sum of Probability * Value. In this case, probability is calculated by dp for a given length and value is the length itself. Since the list must contain all elements, we get that our answer is sum of dp[len][n] * len.

The trick used here is to consider precision: the precision required is very small. This means, when values dp[len][n] * len becomes almost zero, we can stop the simulation, since it won’t affect the result anyway (well, actually it would affect the result, but for the given precision, it doesn’t matter). In our solution, we consider almost zero to be < 1e-4.

We’re left with recurrences of dp. An element is being chosen with probability 1 / n. We consider dp[0][0] = 0. Suppose we’ve calculated dp[i][j] and we want to update the results for dp[i + 1][li]. What can be the recurrences?
[/li]
Well, to find them, let’s analyze the two cases we have.

  • We don’t add a new element

This means, we need to add one of existing j elements. The probability to pick one of existing j elements is j / n. So we get

dp[i + 1][j] += dp[i][j] * (j / n)

  • We add a new element

We can choose only (n - j) elements. The probability to pick one of them is (n - j) / n.

So we get dp[i + 1][j + 1] += dp[i][j] * ((n - j) / n).

Pay attention when you calculate dp[i][n]. You are not allowed to add result from dp[i - 1][n], since the list of length i - 1 already contains all n elements. This approach should be used for n <= 400 (or something like this). For larger values, it should time out.

Large values of n

There are two ways to solve for larger values. The first one is the most obvious: run your program locally, then store answers in a file, put answers in an array in your program and simply output relevant content of the array.

The not so obvious one is to notice the answer is about n * ln(n) for large values. For those who like proofs, we leave this one as a homework for you :slight_smile:

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution to be updated soon
Tester’s solution

1 Like
2

I used a different approach, without DP. The no of tries per coupon is the Nth Harmonic Number (1 + 1/2 + 1/3 + … + 1/N).

The total no of tries is therefore N * no of tries per coupon.

You can find the proof here: http://en.wikipedia.org/wiki/Coupon_collector's_problem#Solution

12 Likes
3

Hm, knowing that was a big advantage :wink: Not my case…

1 Like
4

Both practice and contest links currently pointing to RRJAM, please correct it.

1 Like
5

fixed already :wink:

1 Like
6

I solved it in a simpler manner. I used a recurrence relation that i derived.

ans[i]=ans[i-1]/(i-1)*i+1

I wasnt sure it was correct as i did it in a hurry after being plagued by WA’s on Matrix problem (I was outputting the number of unique vectors there :stuck_out_tongue: ) but it got AC.

3 Likes
7

After analysing above recurrence relation, “ans[i]=ans[i-1]/(i-1) x i+1”, found a way to explain, we have Exp Val = Summation { Val x Prob }, Val = Exp / Prob, so the series for ans[i] and ans[i-1] will be same except ans[i] requiring one more chance to play i’th song, Val_i = Exp(i-1)/Prob(i-1) + 1/Prob(i), now multiply by the Prob(i), Exp(i) = Prob(i) x Val(i) = Exp(i-1)/(i-1) x i + 1, which is your recurrence relation.

1 Like
8

Is the code described in the tester’s solution same as described in the editorial above?
I don’t quite understand the tester’s solution.
What is this code snippet doing?

for (int i = 1; i <= 3000; i++) {
	c[i][i] = 0;

	for (int j = i - 1; j >= 0; j--)
		c[i][j] = c[i][j + 1] + 1.0 * i/(i-j);
}

And why do we access c[n][0] for the final solution?

1 Like
9

There is also a formula for this question. As you can see a harmonic sequence is formed.

S = log(n+0.5) + 0.5772 + 0.04021/(n*n + 0.8848).

Integration is used to derive this formula. U can read about it from here.

Click here for further details

10

@sampritipanda can you please explain the approach of your solution

11

would dat i hav learned it before…:wink:

12

For those who like proofs, we leave
this one as a homework for you :slight_smile:

Why didn’t you leave the entire editorial as homework for us?

You are being paid to write editorials. Your editorials are expected to be complete. :frowning:

6 Likes
13

Pretty sure they aren’t paid for the editorials. Anyways, you can find the proof here: http://en.wikipedia.org/wiki/Coupon_collector’s_problem#Solution

14

What is Prob(i) in this?

15

@sampritipanda They are paid to write editorials. $100 for cook-off editorials. http://www.codechef.com/problemsetting#Editorials_Writing

2 Likes
16

Ok, Didn’t know that. Thanks.