Recover Numbers from Pair Sums
Autumn Tournament (2022)
Submission name: recover.cpp
Problem summary
Recover positive integers a[0]...a[n−1] below 2000 from equations a[i]+a[j]=s. Any valid reconstruction is accepted; indices in this problem are 0-based. A solution is guaranteed.
Input
n on the first line, m on the second, then m triples i j s with i<j.
Output
One valid sequence in index order.
Constraints
2 < n < 500; 2 < m < 2000; n ≤ m; 1 ≤ a[i] < 2000.
Worked example
Original statement sample.
Input
4 5 0 1 5 1 2 6 0 2 7 1 3 8 2 3 10
Output
3 2 4 6
Solution analysis
- Represent every equation as an undirected edge labeled by its sum. Once one vertex value is chosen, an adjacent vertex is forced: value[next]=sum−value[current]. Process connected components independently.
- For each unassigned component root, try its possible values 1 through 1999. A BFS propagates all forced values. Reject a trial if a value leaves [1,1999] or an already assigned endpoint disagrees with an equation. Keep the first valid trial. The small value bound makes this direct search practical.
- In the sample, trying a[0]=3 gives a[1]=2 and a[2]=4. Their edge verifies 2+4=6, and a[3]=6 satisfies the remaining sums. An isolated vertex, if present, may simply receive 1.
Why it works
Every valid solution has some root value in the tried range. Given that value, every path forces the values of all reachable vertices; consistency checks reject exactly conflicting trials. Therefore a valid trial must eventually succeed in every component, and independent component solutions combine into a valid full sequence.
Watch out. Do not assume the graph is connected or that the solution is unique. Check all edges, not only a spanning tree. Values are strictly positive and strictly below 2000.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every valid solution has some root value in the tried range. Given that value, every path
// forces the values of all reachable vertices; consistency checks reject exactly conflicting trials.
#include<iostream>
#include<queue>
#include<utility>
#include<vector>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n,m;
cin>>n>>m;
vector<vector<pair<int,int>>>graph(n);
for(int edge=0;edge<m;edge++){
int u,v,sum;
cin>>u>>v>>sum;
graph[u].push_back({v,sum});
graph[v].push_back({u,sum});
}
vector<int>answer(n,0);
for(int root=0;root<n;root++){
if(answer[root]!=0){
continue;
}
vector<int>component;
vector<bool>seen(n,false);
queue<int>pending;
pending.push(root);
seen[root]=true;
while(!pending.empty()){
int u=pending.front();
pending.pop();
component.push_back(u);
for(auto[v,sum]:graph[u]){
(void)sum;
if(!seen[v]){
seen[v]=true;
pending.push(v);
}
}
}
for(int candidate=1;candidate<2000;candidate++){
for(int u:component){
answer[u]=0;
}
answer[root]=candidate;
pending=queue<int>();
pending.push(root);
bool valid=true;
while(!pending.empty()&&valid){
int u=pending.front();
pending.pop();
for(auto[v,sum]:graph[u]){
int forced=sum-answer[u];
if(forced<1||forced>=2000){
valid=false;
break;
}
if(answer[v]==0){
answer[v]=forced;
pending.push(v);
}
else if(answer[v]!=forced){
valid=false;
break;
}
}
}
if(valid){
break;
}
}
}
for(int i=0;i<n;i++){
if(i>0){
cout<<' ';
}
cout<<answer[i];
}
cout<<'\n';
}