Difficulty : Medium
Pre-requisites : DP
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] 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(N2), because the answer for the test cases with K larger than N2 is zero.
Setter’s solution: link
Tester’s solution: link