Расчет ожидаемого числа инверсий в изменяющемся массиве

Question

Проблема: У нас есть массив размером n и мы разрешено выполнять в большинстве K операций, где каждая операция может быть

1. уменьшить количество инверсии на 1.
2. сделать случайную перетасовку всего массива.

Моя проблема заключается в выполнении операций K таким образом, чтобы ожидаемое количество инверсий в конечном массиве было сведено к минимуму.

Ограничения:
100е testcases с
н K < N (N-1)/2

Мой подход: Я имею в виду динамическое программирование решение. Я могу рассчитать вероятности наличия точно e инверсий в массиве размером n с использованием чисел махонов. Я также заполняю массив dp[k+1][1+n(n-1)/2] row wise, так что dp[i][j] обозначает минимальные ожидаемые инверсии в массиве с j инверсиями после выполнения i операций, а затем с его использованием я могу сгенерировать минимальное ожидаемое значение для операции (i+1)<sup>th</sup> для всех возможных инверсий в массиве.

Проблема с этим подходом Вероятности неточны из-за ограничения удвоений в C++, и этот алгоритм равен O(kn<sup>2</sup>) для каждого тестового примера, который очень медленный.

Например:
Вероятность не имеющая инверсии в массиве размера 100 = 1.0/factorial(100) ~ 10<sup>-160</sup> (я думаю, что есть отсутствие точности здесь).

Я думаю, что есть некоторый точный и эффективный подход. Пожалуйста, предложите несколько идей.

Спасибо

Answer 1

Для того, чтобы ответить на ваш вопрос, вы будете нуждаться, чтобы быть в состоянии вычислить ожидаемые #inversions предполагается, что вы K движется влево и при условии, что на к-й ход вы перетасовать, а затем вы решаете остановить перетасовку (а затем просто вычесть 1) или продолжить перетасовку в зависимости от того, сколько инверсий вы получите после того, как вы перетасовываете. Это легко, если у вас осталось только два хода, а текущие # инверсии больше n (n-1)/4. В основном вы сначала перетасовываете, а затем останавливаете перетасовку и вычитаете 1 для своего второго хода, если число инверсий равно n (n-1)/4 или ниже после первого перетасовки, и вы снова перетасовываете, если количество инверсий больше n (n-1)/4 после первого перетасовки. Для более чем 2 ходов все сложнее, потому что на k-м ходу, если вы перетасовываете, вы можете выбрать верхнюю границу Nk по числу инверсий Nk, для которых вы остановитесь и просто вычтите 1 после этого, и вам нужно оптимизировать этот Nk так что ожидаемое количество инверсий минимально общее. Очевидно, если k больше, то Nk следует выбирать меньше, но вопрос в том, насколько. Если вы можете вычислить, что Nk (для каждого k), то вы решите свою проблему.

Моя интуиция заключается в том, что вы можете решить для Nk для всех k = 1,2, ..., K по существу O (nK) раз, используя какую-то рекурсивную формулировку. Я уточню, если я выясню детали. Если это правда, это означает, что вы можете решить ожидаемое количество инверсий в основном O (nK).