HackerRank Probability – Lazy Sorting

Challenge: Lazy Sorting

Subdomeniu: Probability (probability)

Scor cont: 30.0 / 30

Submission status: Accepted

Submission score: 1.0

Submission ID: 464726194

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/lazy-sorting/problem

Cerinta

Logan is cleaning his apartment. In particular, he must sort his old favorite sequence, $P$, of $N$ positive integers in nondecreasing order. He's tired from a long day, so he invented an easy way (in his opinion) to do this job. His algorithm can be described by the following pseudocode:

    while isNotSorted(P) do {	
        WaitOneMinute();
        RandomShuffle(P)
    }

Can you determine the expected number of minutes that Logan will spend waiting for $P$ to be sorted?

Input Format

The first line contains a single integer, $N$, denoting the size of permutation $P$.		
The second line contains $N$ space-separated integers describing the respective elements in the sequence's current order, $P_0, P_1, \ldots, P_{N-1}$.

Output Format

Print the expected number of minutes Logan must wait for $P$ to be sorted, correct to  $6$ decimal places.

Constraints

- $2 \le N \le 18$
- $1 \le P_i \le 100$

Cod sursa

#!/bin/python3

import math
import os
import random
import re
import sys

def solve(P):

    if P == sorted(P):
        return 0
        
    counts = [P.count(i) for i in list(set(P))]
    n_perm_w_repetitions = int(math.factorial(len(P))/math.factorial(counts[0]))
    for c in counts[1:]:
        n_perm_w_repetitions = int(n_perm_w_repetitions/math.factorial(c))
    ev = n_perm_w_repetitions
    return "%.6f" % round(ev)
if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    P_count = int(input().strip())

    P = list(map(int, input().rstrip().split()))

    result = solve(P)

    fptr.write(str(result) + '\n')

    fptr.close()