Recover Numbers from Pair Sums
National Olympiad — National round (2019 season)
Submission name: pairwise.cpp
Problem summary
Given the sorted multiset of all pair sums of N positive integers, count the possible sorted original sequences and output the lexicographically smallest.
Input
N, then N(N−1)/2 sorted pair sums.
Output
The number of original sequences, then the lexicographically smallest sorted sequence.
Constraints
3 ≤ N ≤ 500; 1 ≤ original value ≤ 10⁹; the supplied sums come from at least one sequence.
Worked example
An independently prepared example for this explanation.
Input
3 3 4 5
Output
1 1 2 3
Solution analysis
- Write the unknowns as a1≤a2≤… . The two smallest sums are a1+a2 and a1+a3. If we guess a2+a3, then a1 is half of their sum minus that guess. The guessed sum must occur among the first N sums: all sums not using a1 are at least a2+a3, while only N−1 pairs use a1.
- For every distinct positive integral candidate a1, reconstruct greedily. In the remaining pair-sum multiset, the smallest unremoved sum must be a1+the next unknown value. Append that value and remove its sums with every previously recovered value. Missing sums invalidate the candidate.
- For sums 3,4,5, taking 5 as a2+a3 gives a1=(3+4−5)/2=1. The smallest remaining sums force 2 and then 3. Other guesses do not yield a valid positive integral reconstruction. Candidate a1 values are deduplicated so repeated input sums cannot duplicate the answer.
Why it works
The first two sums have the stated form even with duplicate values. Every true a1 is generated because its a2+a3 appears within the first N sums. After all pair sums among recovered values have been removed, the smallest remaining sum uses the smallest value a1 and the smallest unrecovered value; all other remaining pairs are no smaller. Thus reconstruction is forced for a fixed a1. Exact multiset subtraction validates necessity and sufficiency, and every sorted sequence is counted once.
Watch out. Pair sums are a multiset; remove multiplicities one at a time. Preserve duplicate original values. Use 64-bit arithmetic for calculating candidates and pair sums.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<set>
#include<unordered_map>
#include<vector>
// Algorithm: Write the unknowns as a1≤a2≤… .
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin>>n;
int pairs=n*(n-1)/2;
vector<long long>sums(pairs),uniqueSums;
for(long long&sum:sums){
cin>>sum;
}
uniqueSums=sums;
uniqueSums.erase(unique(uniqueSums.begin(),uniqueSums.end()),uniqueSums.end());
unordered_map<long long,int>index;
index.reserve(uniqueSums.size()*2);
for(int i=0;i<static_cast<int>(uniqueSums.size());i++){
index[uniqueSums[i]]=i;
}
vector<int>original(uniqueSums.size());
for(long long sum:sums){
original[index[sum]]++;
}
set<long long>candidates;
for(int j=2;j<min(n,pairs);j++){
long long twice=sums[0]+sums[1]-sums[j];
if(twice>0&&twice%2==0){
candidates.insert(twice/2);
}
}
vector<long long>best;
int answer=0;
for(long long first:candidates){
vector<int>remaining=original;
vector<long long>values(1,first);
int smallest=0;
bool valid=true;
while(static_cast<int>(values.size())<n&&valid){
while(smallest<static_cast<int>(remaining.size())&&!remaining[smallest]){
smallest++;
}
if(smallest==static_cast<int>(remaining.size())){
valid=false;
break;
}
long long next=uniqueSums[smallest]-first;
if(next<values.back()||next>1000000000){
valid=false;
break;
}
for(long long value:values){
auto it=index.find(value+next);
if(it==index.end()||!remaining[it->second]){
valid=false;
break;
}
remaining[it->second]--;
}
values.push_back(next);
}
if(valid){
answer++;
if(best.empty()||values<best){
best=values;
}
}
}
cout<<answer<<'\n';
for(int i=0;i<n;i++){
cout<<(i?" ":"")<<best[i];
}
cout<<'\n';
}