Вопрос:
You are given an array A = [1, 2, 3, ..., n]:
How many sequences (S1) can you get after exact k adjacent swaps on A?
How many sequences (S2) can you get after at most k swaps on A?
An adjacent swap can be made between two elements of the Array A, A[i] and A[i+1] or A[i] and A[i-1].
A swap otherwise can be between any two elements of the array A[i] and A[j] ∀ 1 ≤ i, j ≤ N, i ≠ j.
Алгоритм
Sub-problem 1: How many sequences(S1) can you get after exact k adjacent swaps on A?
<==> How many sequences can turn into [1, 2, 3, .. n] after k adjacent swaps.
What's the minimal adjacent swaps need to make it sorted? For every adjacent swaps, we can at most decrease the inversions by 1. We can first choose 1 to the 1st position, then 2 to the 2nd position, and then every swap, we can decrease the inversions by 1.
Because we can only swap even times to make the sequences unchanged.
<==> How many permutations have (k - 2 * i) inversions?
We can set dp[i, j] = The number of permutations of [1, 2,.. i] which the inversions are equal to j.
dp[i, j] = sum {dp[i - 1, j - k], 0 <= k <= i - 1 && k <= j}.
We can speed up this dp by using accumulated sum. O(n3) ==> O(n2)
Sub-problem 2: How many sequences(S2) can you get after at most k swaps on A?
We can set dp[i, j] = The number of permutations of [1, 2, ..., i] we can get if we swap exact j times.
dp[i, j] = dp[i - 1, j] + (i - 1) * dp[i - 1, j - 1]
// append the i to the previously genereated permutations
// swap j with each elements of 1 to i - 1.
You can easily figure out no duplicate exsits.
The answer will be sum{dp[n, j], 0 <= j <= k}.
Не понимаю алгоритм пчоему сумма и инверсия. И при чем здесь инверсия
Инверсия тут - это из комбинаторики. Инверсия - это когда 2 элемента не в том порядке. Количество инверсий - это сколько пар элементов стоят не так. В массиве (1,2,3,4) инверсий 0. В массиве (1,4,3,2) инверсий 3: 4 и 3, 4 и 2, 3 и 2 - вот эти 3 пары идут по убыванию, вместо нормального порядка. Оставшиеся 3 пары стоят как надо.
Простой
Простой
