HackerRank Probability – Assignment Problem

Challenge: Assignment Problem

Subdomeniu: Probability (probability)

Scor cont: 50.0 / 50

Submission status: Accepted

Submission score: 1.0

Submission ID: 464753394

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/assignment/problem

Cerinta

Calvin has a math assignment at school where he has to evaluate a lot of expressions. Calvin decides to not to waste much of his time. There are $M$ expressions overall. By looking at Susie’s answers, Calvin has figured that the answers to all questions form a non decreasing sequence. 

He decides that all his answers are going to be between $1$ and $N$ (inclusive). He fills his answer sheet with a random non-decreasing sequence of length $M$ where each element is between $1$ and $N$. 

Here is the part where the real problem starts for Calvin. He does not want to choose a large value of $N$, because, he will have a lot of options to choose from. Also, if he chooses a very small value of $N$, a lot of answers would become equal and the teacher will become suspicious.  

If $x = \max_{1≤i≤N}(f(i))$, f(i) being the frequency or number of times $i$ occurs in the sequence of $M$ values he picked. Calvin wants to find out [expected value](http://en.wikipedia.org/wiki/Expected_value) of $x$. Help him solve the problem.  

For example, if $M = 3$ & $N = 3$, the possible sequences are:  

    1 1 1 (x = 3)  
    1 1 2 (x = 2)  
    1 1 3 (x = 2)  
    1 2 2 (x = 2)  
    1 2 3 (x = 1)  
    1 3 3 (x = 2)  
    2 2 2 (x = 3)  
    2 2 3 (x = 2)  
    2 3 3 (x = 2)  
    3 3 3 (x = 3)  

expected value of $x = 2.2$

**Input Format**  
The first line contains an integer $T$ which refers to the number of test cases. $T$ lines follow, each containing $2$ numbers, $M$ and $N$ for the corresponding test cases.  

**Constraints**  
$1 \le T \le 15$  
$1 \le M \le 250$  
$1 \le N \le 10^9$  

**Output Format**  
Output $T$ lines, each containing answer to the corresponding test case. Error of upto $10^{-3}$ is allowed.  

**Sample Input**  

    4
    1 5
    3 3
    2 9
    9 6

**Sample Output**  

    1.0000000000
    2.2000000000
    1.2000000000
    4.3146853147
    
**Explanation**  
For second testcase we have  

$$\begin{align*}
\text{Seq} && \text{Freq} \\\
111 && 3 \\\
112 && 2 \\\
113 && 2 \\\
122 && 2 \\\
123 && 1 \\\
133 && 2 \\\
222 && 3 \\\
223 && 2 \\\
233 && 2 \\\
333 && 3 \\\
\end{align*}$$  

$$\begin{align*}
E(x) &= \sum P_x \times x \\\
&= P_1 + 2P_2 + 3P_3 \\\
&= \frac{1}{10} + \frac{2 \times 6}{10} + \frac{3 \times 3}{10} \\\
&= \frac{22}{10}
\end{align*}$$

Cod sursa

#!/bin/python3

import sys


def comb_large_small(n: int, r: int) -> int:
    if r < 0 or r > n:
        return 0
    r = min(r, n - r)
    x = 1
    for i in range(1, r + 1):
        x = x * (n - r + i) // i
    return x


def expected_max_freq(m: int, n: int) -> float:
    # Total weak compositions of m into n parts.
    total = comb_large_small(n + m - 1, m)

    max_j = min(m, n)

    # C(n, j)
    comb_n = [0] * (max_j + 1)
    for j in range(max_j + 1):
        comb_n[j] = comb_large_small(n, j)

    # C(n + r - 1, r)
    comb_nr = [0] * (m + 1)
    for r in range(m + 1):
        comb_nr[r] = comb_large_small(n + r - 1, r)

    # A_k = number of compositions with all parts <= k.
    # E[max] = m - sum_{k=0..m-1} A_k / total.
    sum_a = 0
    for k in range(m):
        step = k + 1
        up = min(max_j, m // step)

        a_k = 0
        for j in range(up + 1):
            r = m - j * step
            term = comb_n[j] * comb_nr[r]
            if j & 1:
                a_k -= term
            else:
                a_k += term

        sum_a += a_k

    num = m * total - sum_a
    return num / total


def main():
    data = sys.stdin.buffer.read().split()
    if not data:
        return

    t = int(data[0])
    out = []
    ptr = 1
    for _ in range(t):
        m = int(data[ptr])
        n = int(data[ptr + 1])
        ptr += 2
        out.append(f"{expected_max_freq(m, n):.10f}")

    sys.stdout.write("\n".join(out))


if __name__ == '__main__':
    main()