Maximum-Weight Pairing of Students
Autumn Tournament (2007)
Submission name: distance.cpp
Problem summary
Pair an even number of points so every point belongs to exactly one pair. Maximize the sum of squared Euclidean distances of the pairs.
Input
Even N, followed by N integer coordinate pairs.
Output
The maximum sum, printed with three digits after the decimal point.
Constraints
2≤N≤22, N even; 0≤x,y≤10000. Coincident points are allowed.
Worked example
Original statement sample.
Input
4 1 1 9 2 10 7 2 6
Output
182.000
Solution analysis
- Precompute weight[i][j]=(xi−xj)²+(yi−yj)². Do not take square roots: the objective already asks for squared distances. A state mask identifies the students still unpaired.
- Choose the first student i in mask. In every complete pairing i has exactly one partner j, so try each other set bit j and add weight[i][j] to the best value after removing both. Memoize the result. Fixing i avoids exploring the same set of pairs in different orders.
- For the sample, pairing(1,1) with(10,7) gives117, and pairing(9,2) with(2,6) gives65, totaling182. The other two complete pairings give smaller sums. An empty mask contributes0; coincident points simply have weight0.
Why it works
Every complete pairing has one unique partner for the first remaining student. Each transition accounts for exactly that pair and leaves an independent smaller pairing problem. Exhausting all partners and applying induction on the number of remaining students therefore gives the optimum.
Watch out. Do not greedily pair the currently farthest points. A sum can exceed signed32-bit range: eleven pairs may each contribute200000000. The exact answer is an integer, so appending .000 avoids floating-point rounding.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
int n;
vector<vector<long long>>weight;
vector<long long>memo;
long long solve(int mask){
if(mask==0){
return 0;
}
long long&answer=memo[mask];
if(answer!=-1){
return answer;
}
int first=0;
while((mask&(1<<first))==0){
first++;
}
answer=0;
int rest=mask^(1<<first);
for(int partner=first+1;partner<n;partner++){
if(rest&(1<<partner)){
answer=max(answer,weight[first][partner]+solve(rest^(1<<partner)));
}
}
return answer;
}
int main(){
cin>>n;
vector<long long>x(n),y(n);
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
weight.assign(n,vector<long long>(n));
for(int i=0;i<n;i++){
for(int j=0;j<n;j++){
long long dx=x[i]-x[j];
long long dy=y[i]-y[j];
weight[i][j]=dx*dx+dy*dy;
}
}
memo.assign(1<<n,-1);
// Each transition removes one complete pair, never one vertex alone.
cout<<solve((1<<n)-1)<<".000\n";
}