 # LDRBRD Editorial, ONCO2020

Setter: Puneet Rai

Medium-Hard

# PREREQUISITES:

Dynamic Programming, Matrix Exponentiation, Maths.

# PROBLEM:

Considering there are N people participating and there are M problems in the contest. What would be the expected number of problems solved by the person at rank K on the leaderboard?

If the expected value is {P/Q} you must print the value {P*Q^{-1} \% MOD}, where {MOD=10^9 + 7}.

# EXPLANATION

Consider the leaderboard as a matrix of size {N*M}.

We define {f(n,m)} as the number of total configurations that are possible if there are n participants and m problems.

{f(n,m) = \sum_{i=0}^{m} {m \choose x}*f(n-1,i)}

This can be calculated in {O(m^3log_2(n))} using matrix exponentiation :-

{\begin{bmatrix} f_{n-1}(0) & f_{n-1}(1) & . & . & . & f_{n-1}(m) \end{bmatrix} * M = \begin{bmatrix} f_n(0) & f_n(1) & . & . & . & f_n(m) \end{bmatrix}}
where, M is {(m+1)*(m+1)} matrix, such that -

{M = \begin{bmatrix}{m \choose 0} & {m \choose 0} & . & . & {m \choose 0} \\ 0 & {m \choose 1} & . & . & {m \choose 1} \\ 0 & 0 & . & . & {m \choose 2} \\ . & . & . & . & . \\ . & . & . & . & .\\ 0 &0 & . & . & {m \choose m} \\ \end{bmatrix}}

Therefore {F_n = F_0 * M^n} and {F_n(i)} is the number of configurations such no one solved more than i problems.

and {F_0 = \begin{bmatrix} 1 & 1 & . & . & . & 1 \end{bmatrix}}

We define {g(n,m,k)} as the number of total configurations that are possible if there are n participants and m problems and the last participant must solve at least k problems.

{g(n , m , k) = F_{0}^{'} * M^n}, where

{F_{0}^{'} = \begin{bmatrix} 0 & 0 & . & 1 & 1 & . & 1 \end{bmatrix}} such that for all {i \geq k}, {F_{0}^{'} (i)= 1}.

We define {h(n , m , k)} as the number of total configurations that are possible if there are n participants and m problems and the first participant must solve at most k problems.

{F_n = F_{0} * M^n}, and -

{h(n , m , k) = F_n(k)}

Now, the answer to the problem is the expected value of the number of problems solved by person k, which can be calculated for each i where i is the number of problems solved by a person at rank k as -

{answer = \sum_{i=0}^m p(k , i) * i }

where {p(i) = } the probability of solving i problems by the person at rank k.

and {p(k , i) = {m \choose i} * g(k-1 , m , i) * h(n-k, m, i) / f(n , m)}

i.e. product of all the possibilities of choosing i problems for rank k , number of ways such that the top {k-1} people solve at least i problems and number of ways such that the bottom {n-k} people solve at most i problems.

Therefore the final answer will be,

{answer = f(n , m)^{-1} * \sum_{i=0}^m {m \choose i} * g(k-1 , m , i) * h(n-k, m, i) * i}

Note - g and h can be calculated in {O(n^2)} by precomputing the matrix M for each of them separately.

So, the total time complexity will be {O(M^3 log_2(N) * T)}.

Time Complexity: {O(T*M^3*log_2(N)})
Space Complexity: O(M^3)
Problem Setter Code: Solution

1 Like