please Explain how to solve RDF

Hi ,
I have solved two easy problem and fire escape problem but unable to figure out solution for RDF . Can any one explain the solution of RDF problem please ?

1 Like

Observation

For any N, if K >= 35 then the result is < 10^-7

Your answer will be judged as correct if its error with in 10^-6. So for all k>=35 you can output 0 as the answer.

Reduced Problem

K is atmost 35

Recursive formula

f(N,K) = 1/N(f(0,K-1) + f(1,K-1) + f(2,K-1) + … + f(N-1,K-1)

Each of 0,1,2,…N-1 can occur with 1/N probability. So the required answer is 1/N times sum of all those.

Base case is when K==0 f(N,K) = N

Reduced formula

f(N,K) = 1/N ( (N-1)*f(N-1,K) + f(N-1,K-1))

Its easy to figure out this if u write f(N,K) and f(N-1,K) (first) formula

Using this formula you can build a DP table DP[N][K]

for(k=0;k<=35;k++) 
   for(n=0;n<MAXN;n++) {
     if(k==0) DP[n][k] = n;
     else if(n==0) DP[n][k] = 0;
     else DP[n][k] = ((n-1)*DP[n-1][k]+DP[n-1][k-1])/n;
}
5 Likes

How to arrive at that Observation ? (I mean you must have done some calculations to arrive at that observation)

The simplest way to get the observation is to do direct calculation and see that results are small.

But I came up with the simple proof of more-or-less exact upper-bound of the maximal K for the given N for which answer is larger than given precision EPS.

Let F(N, K) be the answer for the problem.
It is clear from definition that
F(N, 0) = N
and
F(N, K) = (F(0,K-1) + F(1,K-1) + ... + F(N-1,K-1)) / N for K>0

Let’s derive from here the inequality
F(N, K) <= N / 2^K

The proof is inductive. Base case K=0 is clear from F(N, 0) = N.
The step is as follows
F(N, K+1) = (F(0,K) + F(1,K) + ... + F(N-1,K)) / N <= (0 + 1 + 2 + ... + (N-1)) / N / 2^k = (N-1)/2 / 2^k <= N / 2^(K+1)
and we are done.

Now if F(N, K) >= EPS then
N / 2^K >= EPS or
2^K <= N/EPS or
K <= log2(N/EPS) = log2(N) + log2(1/EPS).
For N=100000 and EPS = 10^-6 it gives approximately
K <= 17 + 20 = 37.
The exact bound is 30.
So this simple inequality gives not bad estimate.

Now the complexity of the solution could be stated as O(N * (log2(N) + log2(1/EPS) )) instead of:
"O(N * maxK) where maxK is small and can be found by experiment".

8 Likes

Absolutely amazing, as usual!!

I learn a lot from your insights and it’s an honor to be learning with one of the best hats off

1 Like

thanks for the solution and explanation . every thing was here “For any N, if K >= 35” awesome .

I am very new in this field I don’t have much idea , can you please explain when you get F(N, K) <= N / 2^K from F(N,0)=N? and what is precision EPS . I searched I got few link but not so clear . can you please give some more link or info about precision EPS please .

EPS is simply the precision used… I believe it refers to Epsilon from Mathematics, to denote very small quantity :slight_smile:

The derivation of the “upper bound” for F(N,K) is in the explanation and it obviously requires some Mathematica insight…

For this particular problem EPS = 10^-6 - the asking precision of the answer.

After wasting some time to find a nlogn solution … inorder to observer any patterns i generated 100 by 100 table … That gave the required info :wink:

//