Median Order-Equivalent Sequence
National Olympiad — Regional round (2020 season)
Submission name: ucongruence.cpp
Problem summary
Sequences are equivalent when every pair of positions has the same less-than, equal-to or greater-than relationship. Among equivalent sequences of length N with values 1…U, output the lexicographic lower median (one-based position floor((familySize+1)/2)).
Input
N U, followed by the sequence.
Output
The median equivalent sequence.
Constraints
1 ≤ N ≤ 1,000,000; 1 ≤ U ≤ 60; all input values lie in 1…U.
Worked example
An independently prepared example for this explanation.
Input
4 26 4 6 6 4
Output
8 17 17 8
Solution analysis
- Compress the d distinct input values into increasing ranks. An equivalent sequence chooses d distinct values from 1…U and assigns them in rank order. Thus the family size is C(U,d), which fits unsigned 64-bit arithmetic for U≤60.
- Lexicographic order chooses the value of the first previously unseen rank encountered in the input, then the next unseen rank, and so on. Greedily try candidate values increasingly. For fixed rank-value assignments, each gap between consecutive assignments independently chooses its remaining rank values: the completion count is the product of binomial coefficients C(valueGap−1,rankGap−1). Include sentinels rank 0=value 0 and rank d+1=value U+1.
- For ranks 1,2,2,1 and U=26 there are C(26,2)=325 choices, so unrank position 163. Trying the first value skips blocks of sizes 25,24,…; the selected first value is 8 and the second is 17. Expanding the ranks gives 8,17,17,8.
Why it works
Every equivalence class member corresponds uniquely to an increasing choice of d values. Fixed assignments split this choice into independent gaps, counted exactly by the binomial products. At each first occurrence, all completions with a smaller candidate value precede all completions with a larger one; skipping their exact counts preserves the target’s position within the remaining block. Induction over first occurrences fixes precisely the desired lexicographic family member.
Watch out. Choose assignments in first-occurrence order, not sorted rank order. Use the lower median for even family sizes. All completion counts are bounded by C(60,30), so unsigned 64-bit arithmetic is sufficient.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
// Algorithm: Compress the d distinct input values into increasing ranks.
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,upper;
cin>>n>>upper;
vector<int>input(n),values;
for(int&value:input){
cin>>value;
}
values=input;
sort(values.begin(),values.end());
values.erase(unique(values.begin(),values.end()),values.end());
int distinct=static_cast<int>(values.size());
vector<int>rank(upper+1);
for(int i=0;i<distinct;i++){
rank[values[i]]=i+1;
}
unsigned long long choose[62][62]={};
for(int i=0;i<=61;i++){
choose[i][0]=1;
choose[i][i]=1;
for(int j=1;j<i;j++){
choose[i][j]=choose[i-1][j-1]+choose[i-1][j];
}
}
vector<int>assigned(distinct+2,-1);
assigned[0]=0;
assigned[distinct+1]=upper+1;
auto completions=[&](){
unsigned long long count=1;
int previous=0;
for(int r=1;r<=distinct+1;r++){
if(assigned[r]==-1){
continue;
}
int freeValues=assigned[r]-assigned[previous]-1;
int freeRanks=r-previous-1;
if(freeValues<freeRanks||freeValues<0){
return 0ULL;
}
count*=choose[freeValues][freeRanks];
previous=r;
}
return count;
};
unsigned long long position=(choose[upper][distinct]+1)/2;
for(int value:input){
int r=rank[value];
if(assigned[r]!=-1){
continue;
}
for(int candidate=1;candidate<=upper;candidate++){
assigned[r]=candidate;
unsigned long long count=completions();
if(position<=count){
break;
}
position-=count;
}
}
for(int i=0;i<n;i++){
cout<<(i?" ":"")<<assigned[rank[input[i]]];
}
cout<<'\n';
}