PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: archit
Editorialist: raysh07
DIFFICULTY:
Easy
PREREQUISITES:
None
PROBLEM:
Given a permutation P, define f(P) = lexicographically smallest possible permutation possible by doing the following steps:
- for each i = 1...N, either skip this, or choose X such that P_X = i or P_{X + 1} = i and then swap P_X and P_{X + 1}.
Find the K^{th} lexicographically smallest permutation such that f(P) = identity permutation.
EXPLANATION:
Let us first try to see when P_1 can be made equal to 1.
Suppose the prefix of values looks like X_1, X_2, .., X_K, 1, and our goal is to get 1 to the first index. On the first swap we will swap k and 1. But on the next steps, we cannot use 1 to swap anymore, we must depend on the other value X_i.
Further, this means that the X_1 > X_2 > X_3 > .. > X_{k - 1} is required because otherwise we miss the chance to swap some X_i with 1.
Further, after this swap, the values X_1, ..., X_{k - 1} can never be used in future swaps except with X_k (because their swap is done, and X_k is blocking from others).
So if k \ge 3, then its bad because X_1, X_2 will remain an inversion in f(P). Thus, k \le 2, i.e. position of 1 is \le 2.
Let us further observe the nature of such permutations. If position of 1 is 1, we can just see it as remove the 1 and a good permutation of size N - 1, where good is defined by f(P)= I.
If position of 1 is 2, then again, we can swap P_1 and P_2, then see it as a good permutation of size N - 1.
Finally, if position of 1 is 3, it looks like X, Y, 1. Here, we first use the swap with i = 1 to get X, 1, Y and then the swap with i = X to get 1, X, Y. Note that unless X = 2, this is also bad because we cannot swap X with 2 after swapping X with 1 on the X-th move.
On the other hand, if X = 2, it looks like 2, Y, 1 and with the 2 swaps of Y and 1, and 1 and 2, we can view it as making good permutation of size N - 2.
To summarize, good permuations are recursively defined as those which start with (1), (X, 1) or (2, X, 1) and then are good with respect to size N - 1 or N - 2 respectively. This means that c_i = 2 \cdot c_{i - 1} + c_{i - 2} where c_i is the number of good permutations of size N.
Finding the K^{th} lexicographically smallest good permutation is not hard after this. Notice that the prefixes can be broken into 4 categories based on lex order: (1), (2, 1), (2, X , 1), (X, 1) where X > 2. The counts of each are c_{i - 1}, c_{i - 2}, c_{i - 2} and c_{i - 1} - c_{i - 2}, so we can essentially determine exactly where K lies and recurse into that case.
N \le 10^3 to allow for potentially quadriatic recursions.
TIME COMPLEXITY:
\mathcal{O}(N) per testcase.
CODE:
Editorialist's Code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)2e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 2e5 + 69;
int dp[N];
void Solve()
{
int n, k; cin >> n >> k;
if (k > dp[n]){
cout << -1 << "\n";
return;
}
// 1 -> dp[n - 1]
// 2 1 -> dp[n - 2]
// 2 X 1 -> dp[n - 2]
// X 1 -> dp[n - 1] - dp[n - 2]
auto rec = [&](auto self, int n, int k, int add){
vector <int> v;
if (n == 0){
assert(k == 0);
return v;
}
if (n == 1){
assert(k == 1);
v = {1 + add};
return v;
}
if (n == 2){
assert(1 <= k && k <= 2);
if (k == 1){
v = {1 + add, 2 + add};
} else {
v = {2 + add, 1 + add};
}
return v;
}
if (k <= dp[n - 1]){
// v = self(self, n - 1, k, add + 1);
// v.insert(v.begin(), 1 + add);
int p = 0;
while (k <= dp[n - p - 1]){
p++;
}
v = self(self, n - p, k, add + p);
vector <int> nv;
for (int i = 1; i <= p; i++){
nv.push_back(add + i);
}
for (auto x : v){
nv.push_back(x);
}
v = nv;
} else if (k <= dp[n - 1] + dp[n - 2]){
v = self(self, n - 2, k - dp[n - 1], add + 2);
v.insert(v.begin(), 1 + add);
v.insert(v.begin(), 2 + add);
} else if (k <= dp[n - 1] + dp[n - 2] + dp[n - 2]){
v = self(self, n - 2, k - dp[n - 1] - dp[n - 2], add + 2);
v.insert(v.begin(), 2 + add);
v.insert(v.begin() + 2, 1 + add);
} else {
v = self(self, n - 1, k - dp[n - 1] - dp[n - 2], add + 1);
v.insert(v.begin() + 1, 1 + add);
}
return v;
};
auto ans = rec(rec, n, k, 0);
for (auto x : ans){
cout << x << " ";
}
cout << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i < N; i++){
dp[i] = 2 * dp[i - 1] + dp[i - 2];
dp[i] = min(dp[i], INF);
}
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}