Connection Status:
Competition Arena > RandomSwaps

RandomSwaps

SRM 338 · 2007-02-07 · by misof

SRM 338 · 2007-02-07 · by misof · Dynamic Programming, Math
Class Name: RandomSwaps
Return Type: double
Method Name: getProbability
Arg Types: (int, int, int, int)
Problem Statement

Problem Statement

Suppose that we have an array with arrayLength distinct elements. A quite common task in programming is to randomly permute this array. Novices who encounter this situation often implement the following algorithm:

  • Choose a positive integer swapCount.
  • swapCount times randomly choose two distinct indices and swap the corresponding elements.

This method of permuting an array is bad, because some permutations of the array will be more likely than others. In this problem, you shall compute how bad this method is for a given situation.

You will be given four ints: arrayLength, swapCount, a and b. Consider the element of the array that initially had the index a. Write a method that will compute the probability that this element will have the index b at the end of the process described above.

Notes

  • The indices of elements that are going to be swapped are generated with a uniform probability distribution, i.e., each pair of indices has got the same probability of being chosen.
  • The indices are zero-based, i.e., the array contains elements with indices 0 to arrayLength-1, inclusive.
  • The returned value must have an absolute or relative error less than 1e-9.

Constraints

  • arrayLength will be between 2 and 1,000, inclusive.
  • swapCount will be between 1 and 100,000, inclusive.
  • a and b will be between 0 and arrayLength-1, inclusive.
Examples
0)
5
1
0
0
Returns: 0.6

There are ten possible pairs of indices to swap: (0,1), (0,2), (0,3), (0,4), (1,2), (1,3), (1,4), (2,3), (2,4), and (3,4). Out of these ten, the last six leave the element 0 untouched. Thus the probability is 6/10.

1)
5
1
0
3
Returns: 0.1

Only the swap (0,3) will move the element from position 0 to position 3. The probability of choosing this swap is 1/10.

2)
5
2
0
0
Returns: 0.4

Now there are two possibilities: Either the 0-th element stays in its place for the whole time, or it is swapped away and back again. The probability of the first possibility is (6/10)^2, for the second possibility it is (4/10)*(1/10).

3)
100
500
3
3
Returns: 0.010036635745123007

For 100 elements, even after 500 swaps, the permutation won't be random enough.

4)
2
1
0
0
Returns: 0.0

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

Coding Area

Language: C++17 · define a public class RandomSwaps with a public method double getProbability(int arrayLength, int swapCount, int a, int b) · 66 test cases · 2 s / 256 MB per case

Submitting as anonymous