PROBLEM LINKS
DIFFICULTY
EASY
PREREQUISITES
Simple Math, Dynamic Programming
PROBLEM
You are given a function random(N), that returns a uniform random integer between 0 and N-1.
You are also given a function RDF defined as follows
RDF(N,K)
repeat K times
N = random(N)
return N
Now, given N and K, find the expected value of RDF(N,K).
QUICK EXPLANATION
Let F(N,K) be the expected value of RDF(N,K).
From the definition of RDF, we can derive the following
- F(N,0) = N
- F(N,K) = ( F(0,K-1) + F(1,K-1) … + F(N-1,K-1) ) / N
Thus, we can write a quick DP to solve the problem
F = Array [0 ... 99999] [0 ... 99999]
for i = 0 to 99999
F[i,0] = i
for j = 1 to K
sum = 0
for i = 1 to N
sum += F[i-1,j-1]
F[i,j] = sum / i
Of course this solution will not work. There is neither enough memory and nor enough time. But, if you tried to implement this approach for smaller values of K, you would get an interesting insight.
The value of DP[n,k] falls exponentially as k rises.
In fact, the value of DP[n,k] is well below the required level of precision, when k > 35. Now, you can run the above for
DP = Array [0 ... 99999] [0 ... 36]
and then print the values from the DP table if K ≤ 36. For all other cases you can print 0.
EXPLANATION
Let us prove this formally. [ Thanks to Anton 
]
We will prove by induction that
F(N,K) <= N / 2K
Base Case
F(N,0) <= N
This is given.
Induction
F(N,K+1) =
( F(0,K) + F(1,K) ... + F(N-1,K) ) / N
Since F(j, K) <= j / 2K for j = 0, 1, ..., N-1
F(N,K+1) <=
( 0/2K + 1/2K ... + (N-1)/2K ) / N
= ( 0 + 1 ... + N-1 ) / N / 2K
= N*(N-1)/2 / N / 2K
= (N-1) / 2K+1
<= N / 2K+1
Hence Proved.
Consequence
F(N,K) <= N / 2K
- F(N,K) increases as N increases.
- F(N,K) decreases as K increases.
We can only increase N up to 99999. At N = 99999, let us find the value of K, beyond which F(99999,K) will be less than our precision goal.
99999 / 2K < 10-6 2K > 1011 K > log2 1011 or, K > 36.54
Thus, at K = 37, already all the values of F(N,K) are less than 10-6.
We can simply calculate the DP till K = 36. Print the values from the DP table if K ≤ 36, or 0 otherwise.
SETTER’S SOLUTION
Can be found here.
TESTER’S SOLUTION
Can be found here.
