SEABUB - Editorial

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

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 ??

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.

1 Like

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.

1 Like

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

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

1 Like

What is D ? Can someone explain more please?

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) ??

3 Likes

@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?

1 Like

Can you please explain the problem statement?

1 Like

@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.

2 Likes

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

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

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

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.

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

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

@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.

@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.

D = sum of previous DP row( DP[J][Q-1] * prob[N][J]). The next row depends only on D, because from the point we start shuffling again(e.g. 3 at 2nd iteration in above case): the optimal answer is just D(the previous DP row sum) - like in above case it is 1/6*1.5 = 0.25 => D = 1.5.