DP #6 Inversions in Permutations

DP+Binary Search+Ordered Set

Inversions in Permutations

Problem Statement: here

Solution:

The editorial is good enough, I would suggest you to read after this one.

So, some parts are taken from editorial itself.

$N\le 500$
$R \leq 200,000$
$K\leq 10^{18}$
$Q \leq 2000$

$Here\; each\; different\; test\; case\; is\; a\; different\; query\; which\; we\; are\; asking.$

$So,\; we\; want\; to\; find\; the\; Kth\; lexicographically\; smallest\; permutation\; using\; [1,N]\; numbers.$

Preprocessing

$We\; will\; build\; 2d\; DP\; table,\; which\; will\; store\; the\; number\; of\; permutations.$

$More\; formally,\; dp[i][j]\; will\; store\; the\; number\; of\; permutations\; using\; numbers\; in\; the\; range$

$[1,i]$ and having exactly j inversions. We will compute this for all i in range [1,500].

Here the value 500 is because maximum value of N is 500.

Another critical observation is that what is the maximum number of inversions I 

can generate using the [1,N] numbers. So, the only permutation with zero 

inversion is: 1 2 3 4 5 6 7 8 9...................N

So, if we move any number from its index to any index below it, it will be an
inversion.More formally, for all indices j, j<i, we have inversions if we swap the
elements of the permutation with zero inversions. 

So, any index i will give at max (i-1) inversions, because it has (i-1) indices behind. 

If, we consider zero based indexing, (i-1) becomes i.

So, total number of inversions is summation i, where i varies from 0 to n-1.

So, for any given i in our dp table, we can have at max i*(i-1)/2 inversions, and that

will be the size of second parameter. 

Constructing the DP table:

Base case : for exactly  zero inversions, the count is 1.

For exactly, the maximum number of inversions, the permutation will become sorted

in decreasing order, and the count is 1 for that case as well.

For having exactly j inversions, we need to think how we can compute it efficiently.

dp[i][j] -> we want count of those permutations where we are using [1,i] numbers 
and exactly j inversions.

dp[n][r]=k=1∑min(n,r+1)​dp[n−1][r−(k−1)] 

This is the recurrence relation we have used. 

Let's understand how does it come. So,we know if we keep any element on the

first position, it will contribute (element - 1) inversions. For, example , if any 

permutation starts with 3, we are sure it has at least 2 inversions, because 1and 2 will 

come somewhere in this sequence and they will form inversion pair with 3.

So basically, we are trying to keep every possible element, let's say k, on first place, 

once we fix that first place, we are now left with a sequence of i-1 integers and 

j - (k-1) inversions. 

One thing to note is that inversions are ordinal. So, which element I am placing 
in front will not decide anything except the amount of inversions it has already done.

So, my k  can vary from 1 to i in this case. But, wait we also want to make sure that 

j - (k-1) does not go negative, What does that mean ?? 

For example, we have i = 6, j = 3. So, for obvious reasons, we cannot place anything 

above 4 in the first place, because if we place 5, it has already done 4 inversions, and

we need only 3 inversions. So, at max my k value should be r+1. So, we take 
minimum of (n,r+1) and calculate the inversion table. 

That was exciting, right?!!

The author's code uptill this part is:

#include<bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> using namespace __gnu_pbds; using namespace std; typedef tree<int ,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update>

ordered_set; #define ll long long #define siz(i) ((i) * ((i) - 1) / 2) const ll INF = 1e18, N = 501; vector<ll> dp[N]; inline ll get_sum(int idx, int l, int r){ l = max(l, 0); r = min(r, siz(idx)); ll sum = 0; for(int i = l; i <= r; i++){ sum += dp[idx][i]; if(sum >= INF) return INF; } return sum; } int main(){ ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0); for(int i = 1; i < N; i++) dp[i].resize(siz(i) + 1); for(int i = 1; i < N; i++){ int s = siz(i); dp[i][0] = dp[i][s] = 1; for(int j = 1; j <= s / 2; j++) dp[i][j] = dp[i][s - j] = get_sum(i - 1, j - i + 1, j); } }

Rest Part - I will continue with this post ahead!!