CHEFONM - Editorial

Author: Misha Chorniy
Tester: Karan Aggarwal
Editorialist: Pushkar Mishra

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.

SAMPLE SOLUTIONS:

4 Likes

Iâ€™m surprised this was the hardest problem of the contest and with so few solutions (not way more than normal). I reformulated swaps to cycle merge/splits immediately, so after I saw how few choices for cycle lengths there are, the rest was just implementation and a standard GEM-DP.

Please someone explain how the expected value equation was derived? Also, please add some more details to the algorithm in the tutorial.

1 Like

Apologies for the delay. I remembered it, but sadly could not get time to work upon it.

We want to know the expected number of swaps we want to make for sorting the permutation P. Let us denote this by E(P).

If the permutation is sorted, then there are no swap required, so E(P) = 0 for P = \{1, 2, \dots, n\}.

Let us see what happens for other permutations. Consider a permutation P. We can choose any two indices (i, j), i < j in it with probability \frac{1}{\frac{n * (n - 1)}{2}}, and swap P_i, P_j and get a new permutation P'. So, expected number of swaps for P will be given by this expression.

E(P) = \frac{1}{\frac{n * (n - 1)}{2}} (E(P') + 1) for each P' obtained by swapping i, j, s.t. i < j.

If you donâ€™t get the crux of this formula, then you can think it like this, if from a state S, you can go to state S' with prob p' and by making x' swaps, then your expected number of swaps in S, will E(S) = p' * (E(S') + x'), for all such S'.

Solving these recurrence relations

Now how to solve these recurrence relations.

Let us take an example for P = [2, 1, 3].
Let us write the equations for E(P) for each P = [2, 1, 3].

\begin{aligned}
E([2, 1, 3]) = \frac{1}{\frac{3 * (3 - 1)}{2}} (E([1, 2, 3] + 1) \
+ \frac{1}{\frac{3 * (3 - 1)}{2}} (E([3, 1, 2] + 1) \
+ \frac{1}{\frac{3 * (3 - 1)}{2}} (E([2, 3, 1] + 1) \
\end{aligned}

\begin{aligned}
\text{So } E([2, 1, 3]) &= \frac{1}{\frac{3 * (3 - 1)}{2}} (E([1, 2, 3]) + E([3, 1, 2]) + E([2, 3, 1]) + 3) \
&= \frac{1}{3} (E([1, 2, 3]) + E([3, 1, 2]) + E([2, 3, 1]) + 3) \
&= \frac{1}{3} (E([1, 2, 3]) + E([3, 1, 2]) + E([2, 3, 1])) + 1 \
\end{aligned}

Let us denote \frac{1}{3} by p for making our formulae slightly less verbose.
So, we get

E([2, 1, 3]) = p * (E([1, 2, 3]) + E([3, 1, 2]) + E([2, 3, 1])) + 1

Similarly, write equations for E([3, 1, 2]), you will get-

E([3, 1, 2]) = p * (E([1, 3, 2]) + E([2, 1, 3]) + E([3, 2, 1])) + 1

Equation for E([2, 3, 1]) will be -

E([2, 3, 1]) = p * (E([3, 2, 1]) + E([1, 1, 2]) + E([2, 1, 3])) + 1

Equation for E([1, 3, 2]) will be-

E([1, 3, 2]) = p * (E([3, 1, 2]) + E([2, 3, 1]) + E([1, 2, 3])) + 1

Similarly write equation for E([3, 2. 1]).

E([3, 2, 1]) = p * (E([2, 3, 1]) + E([1, 2, 3]) + E([3, 1, 2])) + 1

Now, let us write equation for E([1, 2, 3]).
We know that E([1, 2, 3]) = 0, because the permutation is already sorted and no swap is required to swap it.

So, these are the equations we got. We need to solve them and find the value of E([2, 1, 3]).
Note that we have 6 equations and 6 variables.

Note that these equations are cyclic, e.g. E([2, 1, 3]) uses E[2, 3, 1], which uses E([2, 3, 1]) uses
E([2, 1, 3]). These are cycles of length 2. There can as well be cycles of even larger lengths. In summary, your equations are cyclic.

If they would not have been cyclic, you can do a topological sorting of the variables and compute the values of variables starting from the one which depends on nobody, and then going to the ones who depend on some in the reverse topological order.

Now, you can write your equations in form of linear equations. e.g. the above equations will be written as

E([2, 1, 3]) = p * (E([1, 2, 3]) + E([3, 1, 2]) + E([2, 3, 1])) + 1
E([3, 1, 2]) = p * (E([1, 3, 2]) + E([2, 1, 3]) + E([3, 2, 1])) + 1
E([2, 3, 1]) = p * (E([3, 2, 1]) + E([1, 1, 2]) + E([2, 1, 3])) + 1
E([1, 3, 2]) = p * (E([3, 1, 2]) + E([2, 3, 1]) + E([1, 2, 3])) + 1
E([3, 2, 1]) = p * (E([2, 3, 1]) + E([1, 2, 3]) + E([3, 1, 2])) + 1
E([1, 2, 3]) = 0

Put all the variables in the left side and the constants on the right side.
We get

E([2, 1, 3]) - p * (E([1, 2, 3]) - E([3, 1, 2]) - E([2, 3, 1])) = 1
E([3, 1, 2]) - p * (E([1, 3, 2]) - E([2, 1, 3]) - E([3, 2, 1])) = 1
E([2, 3, 1]) - p * (E([3, 2, 1]) - E([1, 1, 2]) - E([2, 1, 3])) = 1
E([1, 3, 2]) - p * (E([3, 1, 2]) - E([2, 3, 1]) - E([1, 2, 3])) = 1
E([3, 2, 1]) - p * (E([2, 3, 1]) - E([1, 2, 3]) - E([3, 1, 2])) = 1
E([1, 2, 3]) = 0

Now, if you consider E(1, 2, 3]), E([1, 3, 2]), \dots, E([3, 2, 1]) as unknown variables, you get 6 linear equations and 6 variables. You can solve them by Gaussian elimination.

Please see the following topcoder forums discussion for seeing an elaborate discussion on this

Please note that I have written in slight hurry. I have marked the answer community wiki. Please feel free to edit obvious typos or mistakes.

7 Likes

Where does 42*N^3 complexity come from?

Youâ€™ll have to solve system of size 42 in worst case, so thatâ€™s more like 42^3 there. And I guess first â€ś42â€ť comes from the fact that youâ€™ll have to solve this system for 42 possible starting positions. Ignoring cases with N<10 (as their systems are smaller) weâ€™ll get 42^4 here.

@likecs: I will update some details tonight, please check back around 12pm IST or so.

3 Likes

Still waiting.

@dpraveen, thank you. The explanation was understandable. Please elaborate a more on the gaussian part as xellos also thinks it is standard problem. But i do not know about solving probability relation using gaussian.

1 Like

Sure, I will do it once I get time.

@dpraveen good explanation !