PROBLEM LINKSDIFFICULTYEASY PREREQUISITESSimple Math, Dynamic Programming PROBLEMYou are given a function random(N), that returns a uniform random integer between 0 and N1. 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 EXPLANATIONLet F(N,K) be the expected value of RDF(N,K). From the definition of RDF, we can derive the following
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[i1,j1] 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
and then print the values from the DP table if K ≤ 36. For all other cases you can print 0. EXPLANATIONLet us prove this formally. [ Thanks to Anton :) ] We will prove by induction that
Base Case
This is given. InductionF(N,K+1) = ( F(0,K) + F(1,K) ... + F(N1,K) ) / N Since F(j, K) <= j / 2^{K} for j = 0, 1, ..., N1 F(N,K+1) <= ( 0/2^{K} + 1/2^{K} ... + (N1)/2^{K} ) / N = ( 0 + 1 ... + N1 ) / N / 2^{K} = N*(N1)/2 / N / 2^{K} = (N1) / 2^{K+1} <= N / 2^{K+1} Hence Proved. Consequence
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 / 2^{K} < 10^{6} 2^{K} > 10^{11} K > log_{2} 10^{11} 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 SOLUTIONCan be found here. TESTER'S SOLUTIONCan be found here.
This question is marked "community wiki".
asked 12 Mar '13, 06:06

Plz elaborate how we got the recurrence F(N,K) = ( F(0,K1) + F(1,K1) ... + F(N1,K1) ) / N answered 13 Mar '13, 15:45
Look: When we have N and K on some step of RDF, then the result after k operations will become F[0,K1] with probability 1/N, F[1,K1] with the same probability,..., F[N1,K1] with probability 1/N. So we can put 1/N out of the brackets and get recurrence F(N,K) = ( F(0,K1) + F(1,K1) ... + F(N1,K1) ) / N. Hope it will help you, feel free to ask if you still need more explanations.
(13 Mar '13, 17:48)
@shinigamiryuk: you have to know something about "expected value"
and from problem statement we know, that for K > 0
(13 Mar '13, 18:54)
Hi, I know about expected value but still I'm missing this equation
(30 Apr '13, 16:21)

Great Editorial...how to formulate the recurrence relation for DP problems?? answered 12 Mar '13, 19:09

guys can you tell what's wrong with my submission? it shows TLE, code is easy readable :) http://www.codechef.com/viewsolution/1939322 answered 14 Mar '13, 03:47

I liked the PROOF part. Which describes about reduction factor! Thanks :)