PROBLEM LINK:
Author: Misha Chorniy
Tester: Karan Aggarwal
Editorialist: Pushkar Mishra
DIFFICULTY:
Hard
PREREQUISITES:
Probability, Expectation value, Gaussian Elimination
PROBLEM:
Given is a permutation of first N numbers. At any point, we can choose 2 numbers at random from the array and swap their positions. We continue this procedure until we have a sorted permutation (sorted ascending). We have to report the expected value of the number of swaps it will take to sort the permutation.
EXPLANATION:
Let us start by thinking of the naĂŻvest algorithm that we can have for solving this problem. That is generally the best way to approach such problems.
So we can start with a recursive routine wherein we make all possible swaps to a permutation, and keep going until we hit a sorted permutation. When we do hit a sorted permutation, we check the number of swaps that it took and increment 1 in the count of ways the permutation can be sorted by that many number of swaps. Once this is done, then for each of the number of swaps that can sort the permutation, we multiply it with its count and then divided by the total number of possibilities that one can have in those many number of swaps. For each swap, there are \frac{N*(N-1)}{2} possibilities. So, this value exponentiated to the number of swaps gives us our denominator. When we add over all possible number of swaps that can sort the permutation, we get our answer (note that denominator grows pretty quickly; so the sum converges).
This approach works! But it is too slow. In fact, it is clearly exponential. We need to reduce the number of recursive steps. How do we do that? We haven’t made use of any math yet. We should because that normally helps in such problems. Let’s make some observations first.
One important mathematical construct to note here is that if E(P) is the expected number of swaps to sort a permutation P, then we have that:
E(P) = (\sum E(P') * \frac{2}{N*(N+1)}) + 1
where P' is the permutation obtained by making one swap in P.
There is a crucial observation to make about this formula: it is cyclic. What this means is that if E(P) is dependent on a certain value E(Q), then that E(Q) is also dependent on value of E(P). For example, E([2, 1, 4, 3]) = E([4, 3, 2, 1]).
This tells us that we need \textit{Gaussian Elimination} to solve the system of equations. But the number of variables for doing gaussian elimination can be large, as large as 10!.
This means that we are missing something. One more crucial observation is that we can represent a permutation by its permutation cycle. So we can make an array of lengths of permutation cycles, sort it in ascending order, and imagine this array to be representing a partition of all the permutations. A partition here refers to sum partitions; for example, 4 has sum partitions as : (1, 1, 1, 1), (1, 3), (2, 2), (4). For the largest possible N, i.e., 10, the number of partitions is just 42. Now we can easily solve this gaussian elimination problem. We now produce permutations of numbers based on the partitions. And from those permutations, we can make all possible swaps, which will be a total of \frac{N*(N-1)}{2}, and solve the gaussian equations.
Please see setter’s solution for implementation details.
COMPLEXITY:
\mathcal{O}(42 * N^3) per test case.