Reconstruct a Permutation from Match Counts — Group A
Autumn Tournament (2025)
Submission name: mummy.cpp
Problem summary
Recover a hidden permutation of0..N−1 by querying other full permutations and receiving only the number of matching positions. Correctness is mandatory; the score also rewards a low average query count across25 hidden permutations.
Source clarification. The official editorial describes candidate elimination combined with binary searches of disjoint swaps. This independently written implementation follows that approach but does not claim the author’s optimized100-point query performance. Editorial: https://infos.infosbg.com/files/Contests/ETI/2025/B/analyses/mummy_analysis.pdf
Input
Official interface: vector<int> findPerm(int N), calling int numMatches(const vector<int>&). The LOCAL mock reads N T, then T hidden permutations.
Output
Return the hidden permutation. The educational LOCAL mock prints each recovered permutation; it reports query counts to standard error.
Constraints
1≤N≤500; official T=25. The subtask score multiplier is3700/max(averageQueries,3700).
Worked example
Educational LOCAL mock using the hidden permutation from the official interaction example. This is not an official stdin/output judge transcript.
Input
4 1 1 3 2 0
Output
1 3 2 0
Solution analysis
- First find a permutation with no matches among the still-unknown positions. Random shuffling has a substantial success probability; a zero response certifies that every displayed unknown assignment is wrong. Keep already discovered correct positions fixed. Maintain a boolean candidate table so that these wrong assignments are never treated as useful new possibilities.
- Form disjoint pairs of unknown positions, requiring at least one cross-assignment in each pair to remain a possible candidate. Swap every pair and query. Relative to the zero-match baseline, each pair contributes0,1 or2 new matches independently. If the response is zero, eliminate all of those cross-assignments and use this newly queried permutation as the next zero baseline.
- If a batch has matches, binary-search its pair list: querying only a half tells exactly how many of its new matches lie there. Recurse only into positive halves; zero halves eliminate candidates without further queries. At a single pair, two matches fix both positions. For one match, swap its first position with a known correct anchor: a drop of2 means the first was correct, otherwise the second was correct. Before any anchor is known, use a third incorrect position: the result drops from1 to0 exactly when the first was correct.
- All queries remain permutations, since they only swap entries. After fixing the discovered positions, the rest still has zero matches, so the next iteration reuses the invariant. For hidden[1,3,2,0], a zero baseline might be[0,2,3,1]. Swapping disjoint pairs allows the oracle response to localize the newly correct assignments rather than testing every possible value-position pair individually.
Why it works
A zero response eliminates only false assignments. Disjoint pair swaps affect disjoint positions, so their match counts add and binary-search counts cannot cancel. The anchor tests distinguish the two one-match possibilities by the uniquely correct value removed from the anchor. Consequently only truly correct positions are fixed. Every zero informative batch removes at least one remaining false candidate; every positive batch fixes at least one position. Once all positions are fixed, the returned permutation is exact. Initial randomized zero-baseline search terminates with probability1; it has no deterministic finite query guarantee.
Watch out. This is not an ordinary stdin problem. Never query a vector with duplicate or missing values. Subtract already fixed matches before interpreting a response. Preserve a zero baseline for unknown positions; otherwise positive and negative match changes could cancel. Randomness affects the score and runtime, not the correctness of an accepted deduction.
Commented C++17 solution
Interactive scored problem. Submit findPerm and its helpers with the official mummy.h grader interface; do not submit the LOCAL mock. Compile with -DLOCAL to run the displayed educational demonstration. The randomized candidate-pair strategy is correct but has no guaranteed full-score query bound; actual average query counts determine its score.
#include<algorithm>
#include<functional>
#include<iostream>
#include<numeric>
#include<random>
#include<utility>
#include<vector>
#ifndef LOCAL
#include"mummy.h"
#endif
using namespace std;
#ifdef LOCAL
vector<int>hidden;
int localQueries=0;
int numMatches(const vector<int>&permutation){
localQueries++;
int matches=0;
for(int i=0;i<static_cast<int>(hidden.size());i++){
matches+=permutation[i]==hidden[i];
}
return matches;
}
#endif
vector<int>findPerm(int N){
vector<int>permutation(N);
iota(permutation.begin(),permutation.end(),0);
if(N==1){
return permutation;
}
static mt19937 random(712367);
vector<char>fixed(N,false);
vector<vector<char>>candidate(N,vector<char>(N,true));
int fixedCount=0;
// Find a baseline with no correct unknown positions.
while(true){
int matches=numMatches(permutation);
if(matches==N){
return permutation;
}
if(matches==0){
break;
}
shuffle(permutation.begin(),permutation.end(),random);
}
while(fixedCount<N){
vector<int>unknown;
for(int i=0;i<N;i++){
if(!fixed[i]){
unknown.push_back(i);
candidate[i][permutation[i]]=false;
}
}
shuffle(unknown.begin(),unknown.end(),random);
vector<char>used(N,false);
vector<pair<int,int>>pairs;
for(int a:unknown){
if(used[a]){
continue;
}
for(int b:unknown){
if(a==b||used[b]){
continue;
}
if(candidate[a][permutation[b]]||candidate[b][permutation[a]]){
pairs.push_back({a,b});
used[a]=used[b]=true;
break;
}
}
}
vector<int>query=permutation;
for(auto[a,b]:pairs){
swap(query[a],query[b]);
}
int added=numMatches(query)-fixedCount;
if(added==N-fixedCount){
return query;
}
if(added==0){
permutation=move(query);
continue;
}
function<void(int,int,int)>locate=[&](int left,int right,int count){
if(count==0){
for(int i=left;i<right;i++){
auto[a,b]=pairs[i];
candidate[a][permutation[b]]=false;
candidate[b][permutation[a]]=false;
}
return;
}
if(right-left==1){
auto[a,b]=pairs[left];
swap(permutation[a],permutation[b]);
if(count==2){
fixed[a]=fixed[b]=true;
fixedCount+=2;
return;
}
int anchor=-1;
for(int i=0;i<N;i++){
if(fixed[i]){
anchor=i;
break;
}
}
vector<int>probe=permutation;
bool firstCorrect;
if(anchor!=-1){
swap(probe[a],probe[anchor]);
firstCorrect=numMatches(probe)==fixedCount-1;
}
else{
int third=0;
while(third==a||third==b){
third++;
}
swap(probe[a],probe[third]);
firstCorrect=numMatches(probe)==0;
}
fixed[firstCorrect?a:b]=true;
fixedCount++;
return;
}
int middle=(left+right)/2;
vector<int>probe=permutation;
for(int i=left;i<middle;i++){
auto[a,b]=pairs[i];
swap(probe[a],probe[b]);
}
int leftCount=numMatches(probe)-fixedCount;
locate(left,middle,leftCount);
locate(middle,right,count-leftCount);
};
locate(0,static_cast<int>(pairs.size()),added);
}
return permutation;
}
#ifdef LOCAL
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,t;
cin>>n>>t;
for(int test=0;test<t;test++){
hidden.resize(n);
for(int&value:hidden){
cin>>value;
}
localQueries=0;
vector<int>answer=findPerm(n);
for(int i=0;i<n;i++){
if(i>0){
cout<<' ';
}
cout<<answer[i];
}
cout<<'\n';
cerr<<"Queries: "<<localQueries<<'\n';
}
}
#endif