Statistics

Problem Statement for "BearSortsDiv2"

Problem Statement

Bear Limak was chilling in the forest when he suddenly found a computer program. The program was a correct implementation of MergeSort. Below you can find the program in pseudocode.


# mergeSort(left,right) sorts elements left, left+1, ..., right-1 of a global array T
function mergeSort(left,right):
    # if there is at most one element, we are done
    if left+1 >= right: return

    # otherwise, split the sequence into halves, sort each half separately
    mid = (left + right) div 2
    mergeSort(left,mid)
    mergeSort(mid,right)

    # then merge the two halves together
    merged = []    # an empty sequence
    p1 = left
    p2 = mid
    while (p1 < mid) or (p2 < right):
        if p1 == mid:
            merged.append( T[p2] )
            p2 += 1
        else if p2 == right:
            merged.append( T[p1] )
            p1 += 1
        else:
            if LESS( T[p1], T[p2] ):
                merged.append( T[p1] )
                p1 += 1
            else:
                merged.append( T[p2] )
                p2 += 1

    # finally, move the merged elements back into the original array
    for i from left to right-1 inclusive:
        T[i] = merged[i-left]

Limak noticed that one part of the implementation was missing: the function LESS. You can probably guess that the function is supposed to return a boolean value stating whether the first argument is less than the second argument. However, Limak is a bear and he didn't know that. Instead he implemented his own version of this function. Limak's function uses a true random number generator. Each of the two possible return values (true, false) is returned with probability 50 percent.


The random values generated in different calls to Limak's function LESS are mutually independent. Note that even if you call LESS twice with the same arguments, the two return values may differ.


After implementing LESS, Limak decided to run his brand new program. He initialized the global array T to contain N elements. Then, he filled the values 1 through N into the array: for each valid i, he set T[i] to i+1. Finally, he executed the function mergeSort(0,N).


Even with Limak's new LESS function, the program never crashes. On the other hand, it does not necessarily produce a sorted sequence when it terminates. In general, when the program terminates, the array T will contain some permutation of the numbers 1 through N.


After running the program many times, Limak has noticed that different output permutations are produced with different probabilities. Your task is to help him learn more about these probabilities. More precisely, your task is to compute the probability that a given sequence will appear as the output of Limak's program.


You are given a int[] sortedSequence with N elements, containing a permutation of 1 through N. Let P be the probability that Limak's program, when run on an array with N elements, outputs this permutation. Return the value log(P), where log denotes the natural (base e) logarithm.

Definition

Class:
BearSortsDiv2
Method:
getProbability
Parameters:
int[]
Returns:
double
Method signature:
double getProbability(int[] seq)
(be sure your method is public)

Notes

  • Your return value must have absolute or relative error smaller than 1e-9.
  • You may assume that for each N and for each permutation P of 1 through N the probability that P appears as the output of Limak's program is strictly positive.

Constraints

  • sortedSequence will contain exactly N elements.
  • N will be between 1 and 40, inclusive.
  • Elements of sortedSequence will be between 1 and N, inclusive.
  • Elements of sortedSequence will be pairwise distinct.

Examples

  1. {1,2}

    Returns: -0.6931471805599453

    Limak is sorting a 2-element sequence. The algorithm will split it into two 1-element sequences and then it will merge those together. While merging, the algorithm will call LESS(1, 2) to "compare" the two elements. If LESS(1, 2) returns true, the resulting permutation will be {1, 2}, otherwise it will be {2, 1}. Therefore, the probability of each of those two permutations is equal to 0.5. The return value is log(0.5).

  2. {1,3,2}

    Returns: -1.3862943611198906

    When {1, 2, 3} is sorted, it is first split into {1} and {2, 3}. After that, in order to obtain {1, 3, 2} in the end, two things must happen, one after another: When {2, 3} is recursively sorted, the result must be {3, 2}. From Example 0 we know this happens with probability 0.5. When merging {1} and {3, 2}, the first call to LESS will be LESS(1, 3). This call must return true. Again, this happens with probability 0.5. Therefore, the probability is 0.5 * 0.5 = 0.25, and the answer is log(0.25).

  3. {10,13,18,2,4,6,24,22,19,5,7,20,23,14,21,17,25,3,1,11,12,8,15,16,9}

    Returns: -57.53121598647546

  4. {1}

    Returns: -0.0

  5. {1,2}

    Returns: -0.6931471805599453

  6. {2,1}

    Returns: -0.6931471805599453

  7. {1,2,3,4,5,6,7}

    Returns: -6.238324625039508

  8. {6,2,4,5,8,1,7,3}

    Returns: -11.090354888959125

  9. {9,8,7,1,5,4,6,2,3}

    Returns: -13.16979643063896

  10. {14,4,5,9,3,6,7,8,10,13,11,16,2,1,15,12}

    Returns: -29.805328764077647

  11. {6,7,3,4,5,13,2,8,9,10,11,17,14,1,15,16,12}

    Returns: -33.96421184743732

  12. {9,19,1,2,8,3,13,18,17,12,16,14,10,11,20,7,21,15,4,6,5}

    Returns: -45.054566736396445

  13. {23,22,19,18,17,13,21,16,5,4,8,20,9,10,11,12,7,6,15,14,3,2,1}

    Returns: -51.986038541995896

  14. {7,16,29,19,11,8,6,12,14,21,2,28,10,15,13,4,26,22,25,30,32,27,5,3,9,23,17,20,24,18,1,31}

    Returns: -85.95025038943322

  15. {1,2,3,4,5,6,7,8,15,10,11,12,13,14,9,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,34,32,33,31,35}

    Returns: -64.46268779207492

  16. {37,36,35,34,33,32,31,30,29,28,27,26,25,24,23,22,21,20,19,18,17,16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1}

    Returns: -72.78045395879425

  17. {40,28,24,37,36,19,34,32,33,31,22,29,39,27,20,13,1,10,30,21,8,15,18,17,16,35,14,25,12,11,23,9,26,7,6,5,4,3,2,38}

    Returns: -110.2104017090313

  18. {27,10,8,5,31,13,29,1,30,32,36,24,39,11,21,22,3,4,15,12,20,2,33,6,37,38,16,28,18,9,25,34,23,19,14,7,35,17,26}

    Returns: -110.90354888959125

  19. {1,26,17,19,5,4,39,8,9,10,11,31,13,14,15,16,3,18,24,20,12,22,23,6,36,2,27,28,29,30,33,32,21,34,7,25,37,38,35,40}

    Returns: -108.82410734791141

  20. {7,37,31,1,21,24,32,36,25,26,28,33,34,17,29,6,3,19,20,27,14,4,16,15,18,35,12,23,10,9,8,38,11,5,30,22,2,13}

    Returns: -105.35837144511169

  21. {10, 13, 18, 2, 4, 6, 24, 22, 19, 5, 7, 20, 23, 14, 21, 17, 25, 3, 1, 11, 12, 8, 15, 16, 9 }

    Returns: -57.53121598647546

  22. {10, 1, 5, 4, 7, 6, 2, 3, 9, 8 }

    Returns: -15.942385152878742

  23. {1, 3, 2 }

    Returns: -1.3862943611198906

  24. {10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40 }

    Returns: -72.0873067782343

  25. {2, 1, 3 }

    Returns: -2.0794415416798357

  26. {19, 4, 33, 39, 10, 16, 12, 2, 11, 30, 15, 38, 18, 35, 22, 5, 13, 24, 37, 21, 8, 27, 20, 36, 17, 23, 6, 34, 28, 9, 25, 29, 14, 7, 1, 3, 31, 32, 26 }

    Returns: -107.43781298679151

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: