PROBLEM LINK:
Setter: Puneet Rai
DIFFICULTY:
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