Connection Status:
Competition Arena > RandomSort

RandomSort

SRM 402 · 2008-05-24 · by srbga

SRM 402 · 2008-05-24 · by srbga · Dynamic Programming, Simple Math
Class Name: RandomSort
Return Type: double
Method Name: getExpected
Arg Types: (vector<int>)
Problem Statement

Problem Statement

You are given a int[] permutation containing a permutation of the first n positive integers (1 through n), and you want to sort them in ascending order. To do this, you will perform a series of swaps. For each swap, you consider all pairs (i, j) such that i < j and permutation[i] > permutation[j]. Among all those pairs, you choose one randomly and swap permutation[i] and permutation[j]. Each pair has the same probability of being chosen. Return the expected number of swaps needed to sort permutation in ascending order.

Notes

  • The returned value must be accurate to within a relative or absolute value of 1E-9.

Constraints

  • permutation will contain between 1 and 8 elements, inclusive.
  • permutation will contain each integer between 1 and n, inclusive, exactly once, where n is the number of elements in permutation.
Examples
0)
{1,3,2}
Returns: 1.0

Exactly one swap is needed.

1)
{4,3,2,1}
Returns: 4.066666666666666

In the first step, any two elements can be swapped.

2)
{1}
Returns: 0.0

This permutation is already sorted, so there's no need to perform any swaps.

3)
{2,5,1,6,3,4}
Returns: 5.666666666666666
4)
{1,2}
Returns: 0.0
111)
{8,7,6,5,4,3,2,1}
Returns: 13.221053196152711

Maximal number of inversions.

112)
{8,7,6,5,1,4,3,2}
Returns: 12.895467847303319

Almost maximal number of inversions.

113)
{4, 1, 2, 3}
Returns: 3.0

3 inversions; 1, 1, or 1 inversion removed.

114)
{1, 4, 3, 2}
Returns: 2.333333333333333

3 inversions; 3, 1, or 1 inversion removed.

115)
{2, 1, 4, 3, 6, 5, 8, 7}
Returns: 4.0

Maximal number of pairwise independent inversions.

116)
{4, 3, 2, 1, 8, 7, 6, 5}
Returns: 8.133333333333333

Two independent 10-inversion groups.

121)
{1, 2, 3, 4, 5, 6, 7, 8}
Returns: 0.0

Longest test with no inversions.

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

Coding Area

Language: C++17 · define a public class RandomSort with a public method double getExpected(vector<int> permutation) · 137 test cases · 2 s / 256 MB per case

Submitting as anonymous