**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 ^{2}**), because the answer for the test cases with

**K**larger than

**N**is zero.

^{2}**Setter’s solution**: link

**Tester’s solution**: link