Casting
Autumn Tournament (2014)
Submission name: casting.cpp
Problem summary
Among n actors, a are tall, b have blue eyes and c have blond hair. Find the smallest or largest possible number having all three characteristics, using only these totals.
Input
Mode 1 for minimum or 2 for maximum, then n, a, b, c.
Output
The requested extreme number of suitable actors.
Constraints
1 ≤ n ≤ 10000; 0 ≤ a, b, c ≤ n.
Worked example
Original statement sample.
Input
2 5 3 4 5
Output
3
Solution analysis
- The intersection cannot exceed any individual group, so its maximum is min(a,b,c). This is attainable by nesting the smaller groups inside the larger ones.
- For the minimum, there are (n−a)+(n−b)+(n−c) missing-characteristic memberships. They can exclude at most that many distinct actors from the triple intersection. Thus at least max(0,a+b+c−2n) actors must have all three traits. Distribute these missing memberships over different actors as far as possible to attain this bound.
- For n=5, a=3, b=4, c=5, at most 3 actors qualify. At least 3+4+5−10=2 qualify because everyone is blond and only one actor lacks blue eyes.
Why it works
The upper bound is attained by nested trait sets. For the lower bound, the union of the three complement sets has size at most min(n,3n−a−b−c), and can attain that size by filling previously uncovered actors first. Its complement therefore has minimum max(0,a+b+c−2n).
Watch out. Clamp the minimum at zero. Mode 1 asks for the minimum, not the maximum.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
using namespace std;
int main(){
int mode,n,a,b,c;
cin>>mode>>n>>a>>b>>c;
if(mode==1){
// Complement sets cover as many actors as possible.
cout<<max(0,a+b+c-2*n)<<'\n';
}
else{
cout<<min({a,b,c})<<'\n';
}
}