Connection Status:
Competition Arena > SpeedingUpBozosort

SpeedingUpBozosort

SRM 784 · 2020-04-23 · by misof

SRM 784 · 2020-04-23 · by misof · Dynamic Programming, Math, Sorting
Class Name: SpeedingUpBozosort
Return Type: double
Method Name: expectedComparisons
Arg Types: (vector<int>, int)
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.

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
0)
{1, 2, 3, 4}
3
Returns: 3.0

You will do three comparisons and discover that the array is sorted.

1)
{1, 1, 2, 2, 2}
5
Returns: 4.0

This array is also sorted.

2)
{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.

3)
{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.

4)
{5, 3, 1, 4, 2}
1
Returns: 284.4791666666661

Bozosort for five distinct elements.

5)
{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!

12)
{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.

Submissions are judged against all 63 archived test cases, of which 7 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class SpeedingUpBozosort with a public method double expectedComparisons(vector<int> A, int numSwaps) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous