Problem: I have an array of size n with Z inversions initially and I am allowed to perform K operations where each operation can be
- decrease the number of inversions by 1.
- make a random shuffle of the array.
My problem is to perform the k operations in such a way that the expected number of inversions in the final array are minimized.
Constraints:
100s of testcases with
1 < n < 100
1 < K < n(n-1)/2
My approach: I am thinking about Dynamic programming based solution. I can calculate the probabilities of having exactly e inversions in an array of size n using mahonian numbers. I also fill an array dp[k+1][1+n(n-1)/2] row wise such that dp[i][j] denotes the minimal expected inversions in the array having j inversions after i operations have been performed and then for each testcase using it I can generate the minimal expected value for (i+1)th operation for all possible inversions in the array.
The problem with this approach the probabilities are not accurate due to the limitation of doubles in c++ and this algorithm is O(kn2) for each test case which is very slow.
Probability of having no inversion in an array of size 100 = 1.0/factorial(100) ~ 10-160,
Even double precision is unable to solve it accurately.
I think that there is some accurate and more efficient approach.
Thank you in advance