Neighbor Encoding
National Olympiad — Regional round (2022 season)
Submission name: permutation.cpp
Problem summary
Count permutations P of 1,…,N consistent with Q: each Qi equals either P(i−1) or P(i+1), with Q1=P2 and QN=P(N−1). Output modulo 1000000007.
Input
N, followed by N values Qi.
Output
The number of consistent permutations modulo 1000000007.
Constraints
2 ≤ N ≤ 10^6; 1 ≤ Qi ≤ N.
Worked example
Official example, transcribed with whitespace restored from the PDF.
Input
5 1 3 1 4 2
Output
3
Solution analysis
- For each value x, intersect the positions where its occurrences allow x to be placed. If x occurs twice, those occurrences must be two positions apart and x is forced into the position between them. More than two occurrences are impossible. A single occurrence at an endpoint also forces x; an internal single occurrence allows one of two positions i−1 and i+1.
- Represent each remaining two-choice value by an edge joining its two allowed positions. These edges form subgraphs of the two paths of odd and even positions. Reserve all forced positions, rejecting any collision. In a path component with E edges there are E+1 vertices; all E edge-values must choose different unreserved endpoints. If there are no reserved vertices there are E+1 assignments, determined by the unused vertex. If there is one reserved vertex there is one assignment, forced outward from it; two or more reserved vertices make assignment impossible.
- Multiply these factors over components. Values absent from Q can fill the N−distinct(Q) remaining positions in arbitrary order, contributing their factorial. In the sample the value 1 is forced to position 2, and the remaining path choices yield three consistent permutations.
Why it works
The candidate intersection for a value is necessary and sufficient for every occurrence to have that value as a neighbor. Forced placements are unique and must not collide. For a path, orient each edge toward its chosen endpoint. Without a reserved vertex, choosing the sole unused vertex uniquely forces all orientations away from it; with one reserved vertex it acts as that unused vertex. More reserved vertices leave fewer available vertices than edges. Thus the component factors count exactly all placements of appearing values. Absent values have no constraints, and their factorial bijectively completes these placements to permutations.
Watch out. Count permutations, not choices of left/right encodings; repeated Q values must refer to the same unique position.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: The candidate intersection for a value is necessary and sufficient for every occurrence to
// have that value as a neighbor. Forced placements are unique and must not collide.
#include<iostream>
#include<numeric>
#include<vector>
using namespace std;
const long long MOD=1000000007;
struct DSU{
vector<int>parent,size;
explicit DSU(int n):parent(n),size(n,1){
iota(parent.begin(),parent.end(),0);
}
int find(int x){
while(parent[x]!=x){
parent[x]=parent[parent[x]];
x=parent[x];
}
return x;
}
void unite(int a,int b){
a=find(a);
b=find(b);
if(a==b){
return;
}
if(size[a]<size[b]){
swap(a,b);
}
parent[b]=a;
size[a]+=size[b];
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
vector<int>first(n+1,-1),second(n+1,-1),count(n+1);
bool valid=true;
int distinct=0;
for(int i=0;i<n;++i){
int x;
cin>>x;
if(count[x]==0){
first[x]=i;
++distinct;
}
else if(count[x]==1){
second[x]=i;
}
++count[x];
}
DSU dsu(n);
vector<int>reserved(n);
for(int x=1;x<=n;++x){
int position=-1;
if(count[x]>2){
valid=false;
}
else if(count[x]==2){
if(second[x]-first[x]!=2){
valid=false;
}
else{
position=first[x]+1;
}
}
else if(count[x]==1){
int i=first[x];
if(i==0){
position=1;
}
else if(i==n-1){
position=n-2;
}
else{
dsu.unite(i-1,i+1);
}
}
if(position!=-1&&++reserved[position]>1){
valid=false;
}
}
vector<int>blocked(n);
for(int i=0;i<n;++i){
blocked[dsu.find(i)]+=reserved[i];
}
long long answer=1;
for(int i=0;i<n;++i){
if(dsu.find(i)!=i){
continue;
}
if(blocked[i]>1){
valid=false;
}
else if(blocked[i]==0){
answer=answer*dsu.size[i]%MOD;
}
}
for(int i=2;i<=n-distinct;++i){
answer=answer*i%MOD;
}
cout<<(valid?answer:0)<<'\n';
}