Challenge: Mathematical Expectation

Subdomeniu: Probability (probability)

Scor cont: 100.0 / 100

Submission status: Accepted

Submission score: 1.0

Submission ID: 464820895

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/mathematical-expectation/problem

Cerinta

Let's consider a random permutation p<sub>1</sub>, p<sub>2</sub>, ..., p<sub>N</sub> of numbers 1, 2, ..., N and calculate the value F=(X<sub>2</sub>+...+X<sub>N-1</sub>)<sup>K</sup>, where X<sub>i</sub> equals 1 if one of the following two conditions holds: p<sub>i-1</sub> < p<sub>i</sub> > p<sub>i+1</sub> or p<sub>i-1</sub> > p<sub>i</sub> < p<sub>i+1</sub> and X<sub>i</sub> equals 0 otherwise. What is the expected value of F?

**Input Format:**  
The first line contains two integers K and N.

**Output Format:**  
Print the expected value of F as an irreducible fraction p / q. Follow sample input for more clarification.


**Constraints:**  
1000 <= N <= 10<sup>9</sup>  
1 <= K <= 5

**Sample input**  

    1 1000

**Sample Output**  

    1996 / 3

Cod sursa

import sys
from math import gcd


def main() -> None:
    data = sys.stdin.read().strip().split()
    if not data:
        return
    k = int(data[0])
    n = int(data[1])

    # E[(#extrema)^K] as exact rational, valid for constraints N >= 1000.
    if k == 1:
        num = 2 * n - 4
        den = 3
    elif k == 2:
        num = 40 * n * n - 144 * n + 131
        den = 90
    elif k == 3:
        num = 280 * n**3 - 1344 * n * n + 2063 * n - 1038
        den = 945
    elif k == 4:
        num = 2800 * n**4 - 15680 * n**3 + 28844 * n * n - 19288 * n + 4263
        den = 14175
    else:  # k == 5
        num = 12320 * n**5 - 73920 * n**4 + 130328 * n**3 - 29568 * n * n - 64150 * n - 5124
        den = 93555

    g = gcd(abs(num), den)
    num //= g
    den //= g
    print(f"{num} / {den}")


if __name__ == "__main__":
    main()
HackerRank Probability – Mathematical Expectation