Complete a Hex
National Olympiad — National round (2010 season)
Submission name: hex.cpp
Problem summary
Six positive integers form a hex if every three contain a pair with gcd greater than 1, but the gcd of all three is 1. Given three integers, find three more minimizing their sum, or report that completion is impossible. Solve two input triples.
Input
Two lines, each containing a b c.
Output
For each input line, a minimum-sum completing triple, or 0 when none exists. Order within a completing triple is unrestricted.
Constraints
1 ≤ a,b,c ≤ 100000. The original scoring gives partial credit to valid nonminimal triples; this solution minimizes the sum.
Worked example
The completing triple may appear in another order. The program’s deterministic optimum has the same minimum sum 212.
Input
65 6 21 5 6 5
Output
55 14 143 0
Solution analysis
- Use a graph on the six numbers, joining a pair whose gcd exceeds 1. Every triple must contain an edge, while no prime may divide three numbers. Check the original triple first. A prime appearing in two original numbers is forbidden in all added numbers; a prime unique to one original can connect it to at most one added number.
- Enumerate the 12 unspecified graph edges: nine original-to-new and three new-to-new. Reject graphs having an independent triple. For each original vertex with d new neighbors, assign its d smallest unique prime factors bijectively to those neighbors, trying all d! assignments. If fewer than d unique factors exist, reject the graph.
- For the new-to-new edges use distinct primes not dividing any original number; assign the smallest required such primes in every permutation. Multiply incident assigned primes to obtain the three added numbers and minimize their sum. In the sample 55,14,143 complete 65,6,21; the second input cannot be completed.
Why it works
In a valid completion a prime divides at most two of the six numbers. Remove powers and unnecessary factors from added numbers: each required gcd edge then needs only one prime. An original-to-new edge must use a prime unique to that original, and different edges incident to the same original need different primes. New-to-new edges must use distinct primes absent from the originals. Replacing a used prime by a smaller available prime preserves exactly the edge graph and cannot increase the sum, so only the smallest required factors and all their assignments need consideration. The enumerated graphs and assignments therefore contain a minimum completion, and every generated graph without an independent triple satisfies both hex rules.
Watch out. The objective is minimum sum, not merely any valid completion. A prime shared by two original numbers cannot appear in an added number. Outputs can differ from the sample while attaining the same optimum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<array>
#include<iostream>
#include<limits>
#include<numeric>
#include<vector>
using namespace std;
using Number=unsigned long long;
using Triple=array<Number,3>;
vector<int>factors(int value){
vector<int>result;
for(int p=2;p*p<=value;p++){
if(value%p==0){
result.push_back(p);
while(value%p==0){
value/=p;
}
}
}
if(value>1){
result.push_back(value);
}
return result;
}
vector<Triple>assignments(const vector<int>&primes,const vector<pair<int,int>>&edges){
int degree=static_cast<int>(edges.size());
if(degree>static_cast<int>(primes.size())){
return {};
}
vector<int>selected(primes.begin(),primes.begin()+degree);
vector<Triple>result;
do{
Triple value={1,1,1};
for(int i=0;i<degree;i++){
value[edges[i].first]*=selected[i];
if(edges[i].second!=-1){
value[edges[i].second]*=selected[i];
}
}
result.push_back(value);
}
while(next_permutation(selected.begin(),selected.end()));
return result;
}
void solve(){
array<int,3>original;
cin>>original[0]>>original[1]>>original[2];
bool fixed[6][6]={};
for(int i=0;i<3;i++){
for(int j=i+1;j<3;j++){
fixed[i][j]=fixed[j][i]=gcd(original[i],original[j])>1;
}
}
if(gcd(original[0],gcd(original[1],original[2]))>1||
(!fixed[0][1]&&!fixed[0][2]&&!fixed[1][2])){
cout<<0<<'\n';
return;
}
vector<int>unique[3];
for(int i=0;i<3;i++){
for(int p:factors(original[i])){
if(original[(i+1)%3]%p!=0&&original[(i+2)%3]%p!=0){
unique[i].push_back(p);
}
}
}
vector<int>fresh;
for(int p=2;fresh.size()<3;p++){
if(factors(p).size()==1&&factors(p)[0]==p&&original[0]%p&&original[1]%p&&
original[2]%p){
fresh.push_back(p);
}
}
Number best=numeric_limits<Number>::max();
Triple answer={};
for(int mask=0;mask<(1<<12);mask++){
bool graph[6][6]={};
for(int i=0;i<3;i++){
for(int j=0;j<3;j++){
graph[i][j]=fixed[i][j];
graph[i][j+3]=graph[j+3][i]=(mask&(1<<(3*i+j)))!=0;
}
}
int bit=9;
for(int i=3;i<6;i++){
for(int j=i+1;j<6;j++){
graph[i][j]=graph[j][i]=(mask&(1<<bit))!=0;
bit++;
}
}
bool valid=true;
for(int i=0;i<6;i++){
for(int j=i+1;j<6;j++){
for(int k=j+1;k<6;k++){
if(!graph[i][j]&&!graph[i][k]&&!graph[j][k]){
valid=false;
}
}
}
}
if(!valid){
continue;
}
vector<Triple>option[4];
for(int i=0;i<3;i++){
vector<pair<int,int>>edges;
for(int j=0;j<3;j++){
if(graph[i][j+3]){
edges.push_back({j,-1});
}
}
option[i]=assignments(unique[i],edges);
}
vector<pair<int,int>>edges;
for(int i=0;i<3;i++){
for(int j=i+1;j<3;j++){
if(graph[i+3][j+3]){
edges.push_back({i,j});
}
}
}
option[3]=assignments(fresh,edges);
for(Triple a:option[0]){
for(Triple b:option[1]){
for(Triple c:option[2]){
for(Triple d:option[3]){
Triple value;
for(int i=0;i<3;i++){
value[i]=a[i]*b[i]*c[i]*d[i];
}
Number sum=value[0]+value[1]+value[2];
if(sum<best){
best=sum;
answer=value;
}
}
}
}
}
}
if(best==numeric_limits<Number>::max()){
cout<<0<<'\n';
}
else{
cout<<answer[0]<<' '<<answer[1]<<' '<<answer[2]<<'\n';
}
}
int main(){
// Enumerate relation graphs, then minimize their prime assignments.
solve();
solve();
}