Soluție HackerRank pentru Assignment Problem, subdomeniul Probability, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.

  • Problemă: Assignment Problem
  • Domeniu: Probability
  • Limbaj: Python 3

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

Cerință

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 ≤ T ≤ 15
1 ≤ M ≤ 250
1 ≤ N ≤ 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) &= ∑ P_x × x
&= P_1 + 2P_2 + 3P_3
&= (1 / 10) + (2 × 6 / 10) + (3 × 3 / 10)
&= (22 / 10)
end{align*}

Cod sursă

#!/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()
HackerRank Probability – Assignment Problem