PROBLEM LINK:
Author: Ayush Ranjan
Tester: Raja Vardhan Reddy
Editorialist: Rajarshi Basu
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming, Knowledge of inversions and permutations.
PROBLEM:
We are given Q queries of the following type:
Print the K^{th} lexicographically smallest permutation of [1,N] with exactly R inversions.
N \leq 500
R \leq 200,000
K\leq 10^{18}
Q \leq 2000
QUICK EXPLANATION:
Initially, build a table dp[N_{max}][R_{max}], where dp[i][j] means number of permutations of length i with exactly j inversions. Reconstruct the solution for each query: greedily take the smallest possible value for each index, as long as enough number of permutations can be constructed while considering the rest of the constraints.
DETAILED EXPLANATION:
I will elaborate on the solution in terms of step-by-step observations.
Initial thoughts about complexity
Since N is just 500 and even R is atmost 2*10^5, nothing much can be guessed about the expected complexity. However, we can say that K will definitely not be in our complexity analysis.
First thoughts
Often, a good way to approach such problems, where we have to print K^{th} lexicographically smallest something, is to think if we can keep greedily fixing elements, as long as the reduced parameters allow for at least X more permutations. Maybe we can do so here?
Observation 1
A curious property is that we can calculate how many permutations of length M (M < N) are possible with R_m (R_m < R) inversions, without needing to know what the first N-M values are.
More explanation
What do I mean by that? Letās say we are dealing with the numbers \{1,2,3,4,5\} and want to see how many permutations with y inversions are possible. Lets say we fix the first number as 3. Now we are left with \{1,2,4,5\}. However, note that the gap is not important really in our calculation of how many permutations with (letās say) x inversions we can get from this set. Our set is essentially the same as \{1,2,3,4\} for all purposes since while counting inversions, we only need to know greater than or less than values. Hence for our purposes, any 4 distinct numbers would have given the same number of permutations.
this hints towards some precomputation. In particular, maybe if we calculate a table dp[N_{max}][R_{max}], where dp[i][j] means number of permutations of length i with exactly j inversions, perhaps it will help us later. Note that we will be calculating this table as a precomputation step, without processing any queries. We donāt need to recompute anything during the queries since for a particular i and j, dp[i][j] is always constant, irrespective of the values already taken.
Building the DP
The DP table can be built on the following recurrence:
dp[n][r] = \displaystyle\sum_{k = 1}^{min(n,r+1)}dp[n-1][r-(k-1)]
The rationale behind arriving at this dp[.][.] recurrence is that we are essentially trying to place k as the first element in our permutation, and considering the rest of the premutation of
n-1 elements with r-(k-1) inversions.
Full Solution
Hint:
Try to recreate the K^{th} smallest permutation, using the dp[.][.] table.
Recreating: Details
Letās say we have a function
getSmallest(int N, int R)which returns the optimal number that should be placed at the start of the N length permutation. Letās say the number placed is x. Observe, this contributes exactly x-1 to the total number of inversions R. Hence, R_{new} = R - (x-1). Now we callgetSmallest(N-1,Rnew), and continue.
Now, also observe that the optimal x is also the smallest value possible which ensures that dp[N-1][R_{new}] \geq K . (unless obviously N=1, in which case it doesnāt matter). This means that had we put some value less than x, then we would have had <k permutations formable using the given constraints.
Implementation 1
A quick thing to note is that the number of permutations will be very VERY large. Hence a trick will be to store any value larger than 10^{18} as -1, as the maximum value of K is 10^{18}, and hence any value larger than that is all the same since we just have to compare it to K while restoring. This means that while computing the dp[.][.], we cannot use prefix sums to make the transitions faster. Instead, we just add the values one by one. This makes for a O(N) transition, and since we have O(N^3) states, the total time taken should be O(N^4). However, if we break out of the loop the first time we encounter a -1, the number of iterations reduces drastically, and it works really fast. Intuition behind this is that the number of permutations with a even say 20 inversions and N=50 (say), is really really large. Hence a large portion of the dp[.][.] table is essentially filled with -1.
Time Complexity
We have a precomputation step of O(N^4), which is effectively O(N^3) amortised due to the break statements. During the queries, we, in worst case, will be looping over all possible numbers in
getSmallest(...). Since we call it O(N) times, our time complexity becomes O(Q*N^2). However, again note that in most cases, most of the first elements of the permutation will just be 1,2,3,4, ... for larger values of N. Hence, it runs much faster in practice.
Challenge:
Do the queries in O(N log N) per query.
QUICK REMINDERS:
Keep using those long long ints.
SOLUTIONS:
Setter's Solution
#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);
}
int t;
cin >> t;
while(t--){
int n, inv;
ll k;
cin >> n >> inv >> k;
if(inv > siz(n) || dp[n][inv] < k){
cout << -1 << "\n";
continue;
}
ordered_set remain;
for(int i = 1; i <= n; i++)
remain.insert(i);
for(int i = 0; i < n; i++){
int st = 1, en = n - i, lst = 1;
while(st <= en && i < n - 1){
int mid = st + en >> 1;
if(inv - mid + 1 < 0)
en = mid - 1;
else if(get_sum(n - i - 1, inv - mid + 1, inv) >= k){
lst = mid, en = mid - 1;
}
else st = mid + 1;
}
k -= get_sum(n - i - 1, inv - lst + 2, inv);
inv -= lst - 1;
lst = *remain.find_by_order(lst - 1);
remain.erase(lst);
cout << lst << ' ';
}
cout << "\n";
}
}
Tester's Solution
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
#define ld long double
const int N=500;
vector<vector< int > >dp(N+5);
vector<vector< __int128 > >sum(N+5);
int done[N+5];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t,n,r,pow8,pow10,pow18,i,j,val1;
__int128 iinf=inf;
__int128 val;
iinf*=inf;
n=N;
//double clk=clock();
r=n*(n-1)/2;
cin>>t;
rep(i,N+5){
dp[i].resize(r+5);
sum[i].resize(r+5);
}
rep(i,r+1){
if(i==0){
dp[1][i]=1;
}
else{
dp[1][i]=0;
}
sum[1][i]=i>0?sum[1][i-1]+dp[1][i]:dp[1][i];
}
f(i,2,n+1){
rep(j,r+1){
val=sum[i-1][j];
if((j-(i-1))>0){
val-=sum[i-1][j-i];
}
val=min(val,iinf);
dp[i][j]=val;
sum[i][j]=j>0?sum[i][j-1]+dp[i][j]:dp[i][j];
}
}
//cout<<(clock()-clk)/CLOCKS_PER_SEC<<"\n";
while(t--){
int k,req,c;
cin>>n>>r>>k;
if(r>(n*(n-1))/2 || k>dp[n][r]){
cout<<-1<<"\n";
continue;
}
rep(i,n){
done[i]=0;
}
req=r;
fd(i,n-1,1){
val=0;
c=0;
rep(j,n){
if(done[j]==0){
val+=dp[i][req-c];
if(val>=k){
break;
}
c++;
}
}
cout<<j+1<<" ";
done[j]=1;
k-=(val-dp[i][req-c]);
req-=c;
}
rep(j,n){
if(done[j]==0){
cout<<j+1<<" ";
}
}
cout<<"\n";
}
return 0;
}
Editorialist's Solution
#include <iostream>
#include <vector>
#include <set>
#include <iomanip>
#include <algorithm>
#include <functional>
#include <stdio.h>
#include <cmath>
#include <queue>
#include <string>
#include <map>
#include <complex>
#include <stack>
#include <set>
#define FOR(i,n) for(int i=0;i<n;i++)
#define FORE(i,a,b) for(int i=a;i<=b;i++)
#define ll long long int
#define vi vector<int>
#define ii pair<int,int>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define pll pair<ll,ll>
#define cd complex<double>
#define vv vector
using namespace std;
const ll INF = 1e18;
const int MAXN = 500+5;
const int MAXR = 2e5+5;
const ll MOD = 1e9 + 7;
ll dp[MAXN][MAXR];
int firstPos[MAXR]; // stores the last i st dp[i][j] > 1e18
void precalc(){
ll psum[MAXR];
FOR(i,MAXR)psum[i] = 0;
FOR(i,MAXN){
if(i == 0)continue;
if(i == 1){
dp[i][0] = 1;
continue;
}
int i2 = (i*(i-1))/2;
FOR(j,i2+2){
//dp[i][j] = dp[i-1][j] + dp[i-1][j-1] + .. + dp[i-1][j-(i-1)];
ll sum = 0;
/*if(psum[j] - (j-i>=0?psum[j-i]:0) > 0){
dp[i][j] = -1;
continue;
}*/
FOR(k,i){
if(sum > INF){
sum = -1;
break;
}
if(dp[i-1][j-k] == -1){
sum = -1;
break;
}
sum += dp[i-1][j-k];
}
if(sum > INF){
sum = -1;
}
dp[i][j] = sum;
}
psum[0] = dp[i][0] == -1;
FORE(j,1,MAXR-1)psum[j] = psum[j-1] + (dp[i][j] == -1);
}
}
int main(){
precalc();
//cout << dp[7][10] << endl;
ios_base::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--){
int n,r;
ll k;
cin >> n >> r >> k;
vi ans;
if(dp[n][r] > -1 and k > dp[n][r]){
cout << -1 << endl;
continue;
}else{
for(int i = n;i>=1;i--){
if(i == 1){
ans.pb(r);
break;
}
FOR(j,i){
//if(r-j < 0)
// cout << i-1 << " " << r-j << " " << dp[i-1][r] << endl;
//if(r < 0)while(1);
if(dp[i-1][r] == -1 or dp[i-1][r] >= k){
ans.pb(j);
break;
}else{
k -= dp[i-1][r];
r--;
}
}
}
}
if(ans.size() < n)return 0;
//cout << ans.size() << endl;
bool taken[n];
FOR(i,n)taken[i] = 0;
FOR(i,n){
int ctr = 0;
FOR(j,n){
if(!taken[j]){
ctr++;
}
if(ctr > ans[i]){
taken[j] = 1;
cout << j+1 << " ";
break;
}
}
}
cout << endl;
}
return 0;
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 
ā¦thanks for the help.