SEABUB - Editorial

[xcwgf666]

Problem link : contest practice

Difficulty : Medium

Pre-requisites : DP

Solution :

Let’s start with the following DP: F[Inv][R]. Its’ value is the minimal possible value of the mathemathical expectation if the current array has Inv inversions and you have R actions left. Basically, in this problem we are interested in the value of DP[number of the inversions in the initially given array][the maximal amount of actions we can take]. How to calculate it fast and correctly?

The first observation is that the value of DP[Inv][0] is Inv. Well, it’s quite obvious that if we have no more actions left, we can only keep the current number of the inversions.

In the general case, when we have some DP[Inv][Q], we can make it equal either to Inv-1, by doing one swap and therefore desreasing the number of inversions or to the sum of DP[J][Q-1] * prob[N][J] over all J from one to N(N-1)/2* - that is simple to understand from itself the definition of the mathematical expectation. Here prob[N][J] is the probability of picking an array consisting of the permutation of the first N integers, containing J inversions.

How to calculate the values of prob[N][K]? Basically, it is equal to the number of permutations of the length N with K inversions divided by N!. So, how to calculate the number of permutations with K inversions? We can pick some permutation with N-1 numbers, and then if we put N at the first position, we get the number of inversions increased by N-1. If we put N, we get the number of inversions increased by N-2 and so on. Following this logic, we can recalculate the sought number of permutations from the values for the smaller N.

If you look precisely at the values of DP[J][R] for some fixed R, you will note (and it’s easy to prove that):

• If J <= R, then DP[J][R] = 0 (i.e. it is possible to make the array sorted by swaps);
• If J > R and J is less than D, DP[J][R] = J-R (i.e. the optimal strategy would be to do only the swaps);
• If J > D, then DP[J][R] = D (because when we do a random shuffle, the current number of inversions doesn’t matter).

Here by D we denote the sum, described above. It is clear that it depends only on R, but not on J.

So, for the fixed R, the DP structure is the following:

0 0 ... 0 1 2 3 ... (integer part of D) D D ... D

So it can be easily maintained, keeping track on the current D. See setter’s and tester’s solutions for the details. The total time complexity for the whole testcase will be O(N²), because the answer for the test cases with K larger than N² is zero.

Setter’s solution: link

Tester’s solution: link

[leon_ken]

Won’t it be the case the for any array, for the expectation of f(A) to be minimum , there can be at most 1 random shuffle
and if it were to happen , that would happen at the start of the k actions ( that means the 1st action would be a shuffle followed by k-1 swaps) ??

[coderfive]

@leon_ken If the shuffle resulted with an array of n*(n-1)/2 inversions, it’s not optimal, so another shuffle is needed. Got the idea?

[d3v3lop3r]

Can you please explain the problem statement?

[leon_ken]

@coderfive, So, suppose in the optimal case, ‘x’ number of shuffles have been
used , and consider the scenario when the x-th (last) shuffle is applied. Now whatever array we had just before x-th shuffle becomes irrelevant as the shuffle gives each permutation with equal probability(it’s like starting afresh). Now ,let P[i] be the number of permutations with i swaps . Now let’s suppose we have
‘z’ number of actions still left.(Clearly z <= k-1). So , now the Expected value of f(A) = Sum( P[i]*(i-z))/n! where i>=z and i<= nC2 .Now , this sum can be minimized when z is maximum i.e z = k-1.

[leon_ken]

just wanted to ask , is there something wrong with the above statement ???

[k0stia]

there is a problem with setter solution. it can not be downloaded.

[tamimcsedu19]

I was also thinkin as @leon_ken said . We take min of inv-k and E[rand_shuffle]-k-1. Whats wrong with this idea ??

[leon_ken]

E[rand_shuffle]- (k-1) is actually wrong because here you would be subtracting k-1 from the possible permutations where the number of swaps is less than k-1.The correct answer should be E[rand_shuffle] - (k-1) + Sum( (P[i])*(k-1-i) )/n! where i < (k-1) and P[i] is the number of permutations where i swaps

[gdisastery1]

Could you please explain the third case more precisely? Am I supposed to shuffle one time or R times?

[anilvarshney1]

I felt that the problem statement was a bit ambiguous. I had two these two interpretations:

1)The set of actions is fixed irrespective of what random permutation you get. For example: Optimal set of actions can be like { random_shuffle, swap(a1,a2) , swap(a3,a4) }. So the set of swaps is fixed.

2)The set of actions can be different depending upon the random permutation we get. In the optimal set for this case, we can perform swaps, which only reduce the inversions for the specific random permutation that we get.

For (1), the solution is pretty straightforward. If we perform a random shuffle, the expected number of inversions is n*(n-1)/4 and after performing a swap this remains constant as in half the permutations this generates an inversion and in half it removes an inversion.

Solution: http://www.codechef.com/viewsolution/4804180

For (2), if we choose to perform random_shuffle, then for remaining (K-1) actions, we can do swaps to reduce the inversions for the random permutation that we get. So final result would be :

E[inversion] = sum { i = K to N*(N-1)/2 } (i - (K - 1)) * Probability[permutation has i inversions]

Solution: http://www.codechef.com/viewsolution/4756477

Both the solutions give wrong answer. I would be really grateful if someone could point out my mistake.

[amitsaharana]

The shuffle being applied depends on the permutation you keep getting. So, after 1 shuffle, we decide to swap the permutations having inversion <= k0 while shuffle remaining and so on.

Consider the following case : 1 3 2 3 2 1.

Here n = 3 , perm. = 3,2, 1 initial inversions = 3.

1. Only swaps => ans = 1

2. One shuffle or two shuffle on all permutations(as you all have been asking) : 1.5(see below you will understand why)

3. Optimal : We shuffle once get 6 permutations according to distribution, 1/6,2/6,2/6,1/6 of number of permutations having inversions = 0,1,2,3 resp. Apply remaining swaps to first 5 permutations -> contribution = 1/6 * 0 + 2/6 * 0 + 2/6 * 1 = 0.3333. Apply shuffle to permutation=3,2,1 => again distribution = 1/36,2/36,2/36,1/36. No action remains. Contribution = 1/36 * 0 + 2/36 * 2 + 2/36 * 2 + 1/36 * 3 = 0.25
   Answer = 0.333+ 0.25 = 0.5833333.

Hence, the we only shuffle some of the permutations after 1 shuffle, that’s what the question and DP is all about.

[anilvarshney1]

From what @amitsaharana said, Interpretation (2) is correct and solution for it is to do the swaps for the remaining actions for only those permutations which have inversions <= (K-1), otherwise perform a shuffle again in the next move and repeat.

[hellman]

Argh, on all tests that I imagined, answers are the same with the solution’s, though getting WA…

[tamimcsedu19]

What is D in editorial ? I don’t understand? what sum described above?

[samfisher]

Can someone explain how we are converting the n^4 DP into n^2

[tamimcsedu19]

What is D ? Can someone explain more please?

[thunderking]

D is “the sum of DP[J][Q-1] * prob[N][J] over all J from one to N*(N-1)/2”.

[coderfive]

@leon_ken, Suppose there’re n elements in the array. The expected inversions of a random shuffle is n*(n-1)/4, with n*(n-1)/2 and 0 being the max and min respectively. If for example, at the first shuffle we
got the inversion of 0, we’re done.
Now, let’s denote the minimum expected number of inversions with k actions with Einv[k] (an array), and P[i] be the number of cases when the array has i inversions.
Let mk = floor(Einv[k-1]+k-1).
mk means that if the current shuffle with inversions more than it, we need another shuffle(if possible), otherwise we accept it.

[coderfive]

@leon_ken,
Then Einv[k] = sum((i-(k-1)) * P[i] / n! for i from k to mk) + sum(P[i] / n! for i from (mk+1) to n*(n-1)/2) * E[k-1].
The formula above is defined recursively. We should observe that Einv[1] = n*(n-1)/4.
The thing is we need to compute the expected value, namely, all the cases we accepted.