please Explain how to solve RDF

general
,
1

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
2

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
3

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

4

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
5

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
6

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

7

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 .

8

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…

9

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

10

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: