cppAcademy
FROM LEARNING TO COMPETING

Real problems.
Your next challenge.

Explore the Group C Olympiad archive.
Choose a topic. Find a challenge. Build your solution.

213 tasks across the Municipal, Regional, and National rounds (2009–2026), plus 4 previously featured problems. 146 tasks have independently written English summaries, analyses, and C++17 solutions; the remaining entries link to Arena. Topic tags are from Arena or our reviewed explanations. Difficulty labels are learning estimates, not official ratings.
GROUP C2016 · HardCombinatorial unranking

Ranked Involutions

National Olympiad — National round

Submission name: perm.cpp

Solve in Editor →

Problem summary

An involution is a permutation a of 1…n satisfying a[a[i]]=i for every i. List all such permutations in lexicographic order, numbered from 1, and output the permutation at rank k.

Input

n k.

Output

The n permutation values, separated by spaces.

Constraints

1 ≤ n ≤ 30; k is a valid one-based rank.

Worked example

An independently prepared example for this explanation.

Input

3 3

Output

2 1 3

Solution analysis

  1. Let f[m] count involutions on m free labels: f[0]=f[1]=1 and f[m]=f[m−1]+(m−1)f[m−2].
  2. Take the smallest unassigned position i. Try each free value j in ascending order.
  3. For j=i, fixing i leaves f[m−1] completions. Otherwise force both a[i]=j and a[j]=i, leaving f[m−2].
  4. Skip whole blocks by subtracting their counts from k; commit the block containing k.

Why it works

Involutions consist only of fixed points and disjoint pairs. At the first unassigned position, candidate values define consecutive lexicographic blocks. The recurrence counts each block, so rank subtraction selects precisely the kth permutation.

Complexity: O(n²) time and O(n) space.

Watch out. Keep the rank one-based. The maximum count f[30]=606917269909048576 fits signed 64-bit arithmetic; this implementation uses a wider internal counter.

Commented C++17 solution

An independently written complete program with standard headers.

// Key idea: Involutions consist only of fixed points and disjoint pairs. At the first unassigned
// position, candidate values define consecutive lexicographic blocks.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
    int n;
    string text;
    cin>>n>>text;
    unsigned __int128 k=0;
    for(char c:text){
        k=k*10+c-'0';
    }
    vector<unsigned __int128>f(n+1);
    f[0]=1;
    if(n){
        f[1]=1;
    }
    for(int i=2;i<=n;i++){
        f[i]=f[i-1]+(i-1)*f[i-2];
    }
    vector<int>a(n+1);
    int free=n;
    for(int i=1;i<=n;i++){
        if(!a[i]){
            for(int j=i;j<=n;j++){
                if(!a[j]){
                    auto ways=j==i?f[free-1]:f[free-2];
                    if(k>ways){
                        k-=ways;
                        continue;
                    }
                    a[i]=j;
                    a[j]=i;
                    free-=j==i?1:2;
                    break;
                }
            }
        }
    }
    for(int i=1;i<=n;i++){
        cout<<a[i]<<(i==n?'\n':' ');
    }
}

Source: Arena Olimpiici ↗