Closest Four Colours
National Olympiad — National round
Submission name: magical.cpp
Problem summary
Choose one colour value from each of four lists, minimizing the difference between the largest and smallest chosen values. Return any optimal four values in list order.
Input
For each of the four lists: its size, then its values.
Output
Four chosen values, one from each list in input order.
Constraints
Each list has 1…100000 values; every value is in 1…100000.
Worked example
An independently prepared example for this explanation.
Input
2 1 9 1 8 1 10 2 2 9
Output
9 8 10 9
Solution analysis
- Sort the four lists and initialize one pointer in each. Evaluate the range of their current values.
- Advance a pointer whose value is smallest. Stop when any list is exhausted.
Why it works
If the current minimum remains selected, advancing any other pointer cannot decrease the maximum or improve the range. Therefore discarding that minimum after evaluating the current tuple cannot discard the only optimum. Repeating proves optimality.
Watch out. Output colour values, not positions. Duplicate colours are allowed.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: If the current minimum remains selected, advancing any other pointer cannot decrease the
// maximum or improve the range. Therefore discarding that minimum after evaluating the current tuple
// cannot discard the only optimum.
#include<iostream>
#include<vector>
#include<algorithm>
#include<tuple>
#include<climits>
using namespace std;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
vector<vector<int>>a(4);
for(auto&v:a){
int n;
cin>>n;
v.resize(n);
for(int&x:v){
cin>>x;
}
sort(v.begin(),v.end());
}
int p[4]={},ans[4]={},best=INT_MAX;
while(true){
int t=0,hi=0;
for(int j=0;j<4;j++){
if(a[j][p[j]]<a[t][p[t]]){
t=j;
}
hi=max(hi,a[j][p[j]]);
}
if(hi-a[t][p[t]]<best){
best=hi-a[t][p[t]];
for(int j=0;j<4;j++){
ans[j]=a[j][p[j]];
}
}
if(++p[t]==(int)a[t].size()){
break;
}
}
for(int j=0;j<4;j++){
cout<<ans[j]<<(j==3?'\n':' ');
}
}