Расчет ожидаемого количества инверсий в изменяющемся массиве
Проблема: У нас есть массив размера n и нам разрешено выступать максимум K операции, где каждая операция может быть
- уменьшить количество инверсий на 1.
- сделать случайное перемешивание всего массива.
Моя задача — выполнить K Операции выполняются таким образом, что ожидаемое количество инверсий в конечном массиве сводится к минимуму.
Ограничения:
100 тестов с
1 < N < 100
1 < К < п (п-1) / 2
Мой подход: Я думаю о динамическом программном решении. Я могу рассчитать вероятность того, что точно e инверсии в массиве размеров n используя числа Махона. Я также заполняю массив dp[k+1][1+n(n-1)/2] грести так, чтобы 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> (Я думаю, что здесь нет точности).
Я думаю, что есть какой-то точный и более эффективный подход. Пожалуйста, предложите несколько идей.
Спасибо
Решение
Чтобы ответить на ваш вопрос, вам нужно уметь вычислять ожидаемые # инверсии, предполагая, что у вас есть k ходов влево, и предполагая, что на k-м ходу вы тасуете, а затем решаете прекратить тасование (а затем просто вычтите 1) или продолжайте перетасовку в зависимости от того, сколько инверсий вы получите после перетасовки. Это легко, если у вас осталось только два хода, а текущее #inversions больше, чем 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 (нК) времени.
Другие решения