Bounded-difference permutations
National Olympiad — Municipal round
Submission name: kperms.cpp
Problem summary
Count permutations of 1 through n in which the absolute difference of every adjacent pair is at most k.
Input
n k.
Output
The exact number of valid permutations.
Constraints
1 ≤ k ≤ n ≤ 9.
Worked example
An independently prepared example for this explanation.
Input
3 2
Output
6
Solution analysis
- Use dp[mask][last] to count ordered prefixes with exactly the selected values.
- Initialize every singleton. Append an unused value only when its difference from last is at most k.
- Sum full-mask states.
Why it works
Every nonempty permutation prefix has a unique predecessor after deleting its last value. The transition therefore counts every valid permutation exactly once.
Complexity: O(2^n n²) time and O(2^n n) space.
Watch out. Order matters. The condition uses absolute difference, not signed difference.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
#include<cmath>
#include<cstdlib>
using namespace std;
int main(){
int n,k;
cin>>n>>k;
vector<vector<int>>dp(1<<n,vector<int>(n));
for(int i=0;i<n;i++){
dp[1<<i][i]=1;
}
for(int mask=1;mask<(1<<n);mask++){
for(int v=0;v<n;v++){
if(dp[mask][v]){
for(int u=0;u<n;u++){
if(!(mask>>u&1)&&abs(u-v)<=k){
dp[mask|(1<<u)][u]+=dp[mask][v]; // Append one unused value.
}
}
}
}
}
int ans=0;
for(int x:dp.back()){
ans+=x;
}
cout<<ans<<'\n';
}