TopCoder Statistics - Problem Statement

Problem Statement

Boris was recently investigating Bozosort. This is a sorting algorithm that operates as follows:

while True:
    1. scan the sequence from the left to the right to check whether it is sorted
    2. if it is, return it
    3. choose two (not necessarily distinct) indices uniformly at random
    4. swap the elements at those indices

Note the following:

In the implementation of step 1, we break the search as soon as we find a pair of consecutive elements such that the first one is strictly greater than the second.
In step 4 the swap always happens, even if it would make the array "less sorted" (i.e., increase the number of inversions)

To his huge surprise, Boris discovered that Bozosort is rather slow. Thus, he came up with a clever optimization: in each iteration of the infinite cycle he will repeat steps 3 and 4 exactly numSwaps times.

Help Boris investigate whether this actually helps. You are given a very short input sequence in the int[] A and the constant numSwaps. Return the expected number of pairwise comparisons the algorithm will make before it returns the sorted sequence.

Definition

Class:: SpeedingUpBozosort
Method:: expectedComparisons
Parameters:: int[], int
Returns:: double
Method signature:: double expectedComparisons(int[] A, int numSwaps)
(be sure your method is public)

Notes

The answer is always finite.
Your return value must have an absolute or a relative error at most 1e-9 to be accepted.

Constraints

A will contain between 1 and 6 elements, inclusive.
Each element of A will be between 0 and 10, inclusive.
numSwaps will be between 1 and 1000, inclusive.

Examples

{1, 2, 3, 4}

3

Returns: 3.0

You will do three comparisons and discover that the array is sorted.
{1, 1, 2, 2, 2}

5

Returns: 4.0

This array is also sorted.
{10, 0}

1

Returns: 3.0

You will make a comparison. Then, you will either generate two equal indices (the swap does nothing) or two distinct indices (the swap makes the array sorted). Each happens with probability 50%. Then, you will make a second comparison. If the array is now sorted, you are done. Otherwise, you are in the same spot as a while ago.
{7, 4}

47

Returns: 3.0

More swaps doesn't change anything in this scenario, the probability of actually swapping the two elements when performing 47 random swaps in a row is still exactly 50 percent.
{5, 3, 1, 4, 2}

1

Returns: 284.4791666666661

Bozosort for five distinct elements.
{5, 3, 1, 4, 2}

3

Returns: 215.35376724261207

Hey, would you look at that, doing more swaps does actually make it run faster on average!
{2, 4, 6, 8, 10, 1}

1

Returns: 1617.9800000000923
{2, 4, 6, 8, 3, 10}

2

Returns: 1356.8906726954058
{6, 5, 4, 3, 2, 1}

1000

Returns: 1236.9999999981378
{1, 2, 4, 3, 5, 6}

1000

Returns: 1238.999999998138
{1, 1, 7, 1, 1, 1}

1000

Returns: 22.999999999999677
{1, 1, 7, 1, 1, 1}

3

Returns: 30.57894736842111
{1, 1, 2, 1}

4

Returns: 12.6

If some elements are identical, we need less luck and generally we'll sort the sequence faster.
{6, 6, 6, 6, 6}

631

Returns: 4.0
{0, 0, 10}

966

Returns: 2.0
{5, 9, 6, 8, 0, 3}

361

Returns: 1237.999999998138
{0, 7, 7, 7, 0}

987

Returns: 26.999999999999872
{8, 8, 0, 4}

805

Returns: 23.99999999999977
{7, 9, 8}

836

Returns: 11.000000000000007
{5, 6, 0}

948

Returns: 11.000000000000007
{3, 5, 7, 0, 10, 4}

618

Returns: 1238.99999999814
{6, 1, 7, 5, 6}

416

Returns: 110.99999999999643
{6, 6, 6}

533

Returns: 2.0
{10, 10, 9}

903

Returns: 7.0000000000000036
{4, 4, 1}

304

Returns: 7.0000000000000036
{9, 9, 9}

546

Returns: 2.0
{6, 6, 5, 3, 0}

41

Returns: 112.0000000171354
{0, 0, 0, 1}

584

Returns: 3.0
{9, 7, 2, 8, 8, 0}

856

Returns: 650.9999999995094
{5, 0, 10}

493

Returns: 10.000000000000009
{5, 4, 4, 4, 4}

944

Returns: 14.999999999999961
{7, 8, 7, 8, 8}

944

Returns: 24.999999999999872
{9, 8, 8, 8}

375

Returns: 9.99999999999997
{9, 9, 7, 9, 7, 7}

562

Returns: 49.999999999998145
{1, 2, 2}

891

Returns: 2.0
{8, 5, 5}

665

Returns: 6.000000000000003
{9, 4, 9, 10}

457

Returns: 22.999999999999766
{2, 2, 2, 2, 2}

302

Returns: 4.0
{4, 4, 4, 4}

80

Returns: 3.0
{0, 1, 2, 9, 6, 10}

308

Returns: 1239.9999999981399
{4, 4, 4, 4, 4}

303

Returns: 4.0
{2, 2, 2, 2, 8, 2}

931

Returns: 24.99999999999954
{1, 6, 9}

256

Returns: 2.0
{6, 6, 6, 6, 6}

11

Returns: 4.0
{0, 0, 10}

9

Returns: 2.0
{9, 9, 6}

9

Returns: 7.000254039223654
{8, 8, 8, 8}

5

Returns: 3.0
{5, 5, 5}

10

Returns: 2.0
{10, 10, 10, 10, 10}

8

Returns: 4.0
{3, 4, 4, 8, 3}

6

Returns: 63.8570015687702
{8, 3, 8, 9, 9, 9}

11

Returns: 129.1721241235709
{10, 2, 0, 8}

5

Returns: 41.4533235581623
{2, 3, 7, 1, 3}

9

Returns: 113.30159595668043
{5, 3, 1, 6, 7, 10 }

1000

Returns: 1236.999999998138
{6, 5, 4, 3, 2, 1 }

1000

Returns: 1236.9999999981378
{6, 5, 4, 3, 2, 1 }

100

Returns: 1236.9999999981378
{5, 3, 4, 2, 1, 6 }

1000

Returns: 1236.9999999981405
{10, 9, 8, 7, 6, 5 }

1000

Returns: 1236.9999999981378
{5, 4, 7, 2, 9, 1 }

994

Returns: 1236.9999999981392
{0, 1, 0, 1, 0, 1 }

1000

Returns: 49.999999999998174
{1, 2, 3, 4, 6, 5 }

1000

Returns: 1240.9999999981387
{2, 10, 3, 7, 9, 8 }

95

Returns: 1237.999999998138
{1, 2, 3, 4, 5, 6 }

511

Returns: 5.0

Statistics

Problem Statement for "SpeedingUpBozosort"

Problem Statement

Definition

Notes

Constraints

Examples