Problem: We have an array of size n and we are am allowed to perform at most K operations where each operation can be
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 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 using it I can generate the minimal expected value for (i+1)<sup>th</sup> 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(kn<sup>2</sup>) for each test case which is very slow.
For example:
Probability of having no inversion in an array of size 100 = 1.0/factorial(100) ~ 10<sup>-160</sup> (I think there is lack of precision here).
I think that there is some accurate and more efficient approach. Please suggest some Ideas.
Thank you
In order to answer your question you are going to need to be able to compute the expected #inversions assuming you have k moves left and assuming that at the kth move you shuffle and then you decide to stop shuffling (and then just subtract 1) or continue shuffling depending on how many inversions you get after you shuffle. This is easy if you only have two moves left and the current #inversions is greater than n(n-1)/4. Basically you shuffle first, and then stop shuffling and subtract 1 for your second move if the number of inversions is n(n-1)/4 or lower after you first shuffle, and you shuffle again if the number of inversions is greater than n(n-1)/4 after you first shuffle. For more than 2 moves though, things get more complicated because at the kth move if you shuffle you can choose an upper bound Nk on the number of inversions Nk for which you will stop and just subtract 1 thereafter, and you need to optimize this Nk so that the expected number of inversions is minimal overall. Obviously if k is larger, then Nk should be chosen smaller, but the question is by how much. If you can compute that Nk (for each k), then you will have solved your problem.
My intuition is that you can solve for Nk for all k=1,2,...,K in essentially O(nK) time, using some sort of recursive formulation. I'll update if I work out the details. If true, it would mean that you can solve for the expected number of inversions in essentially O(nK) time as well.