Nested Cylindrical Cups
Autumn Tournament (2024)
Submission name: cups.cpp
Problem summary
Three cylindrical cups have outer diameters d and wall thicknesses c. A cup fits inside another if its outer diameter is at most the other cup’s inner diameter d−2c. Nest cups into chains, then place the outermost cups side by side. Minimize their total width.
Input
Three lines, each containing the diameter and wall thickness of a cup.
Output
The minimum sum of outer diameters of cups not placed inside another cup.
Constraints
0 < d ≤ 1000; 0 < c < d/2; all values are integers.
Worked example
The example is reproduced from the original tournament statement.
Input
5 2 10 2 3 1
Output
13
Solution analysis
- Describe a nesting by choosing a parent for each cup: either one of the three cups or no parent. A parent is the cup directly containing it. There are only 4³=64 assignments.
- Reject a parent assignment if a cup does not fit, contains itself, or two cups have the same immediate parent. Strictly larger parent diameters rule out cycles automatically. For a valid assignment, sum the diameters of cups with no parent.
- For diameters 5,10,3 and thicknesses 2,2,1, the size-10 cup has inner diameter 6. It can contain either small cup but not both as immediate children. Nesting 5 inside 10 leaves outer cups 10 and 3, giving 13.
Why it works
Any legal nesting consists of chains and therefore appears among the enumerated parent choices. Every accepted choice has fitting parent-child pairs, at most one child per parent, and no cycles because parent diameters strictly increase. It is consequently a legal chain arrangement. Its exposed width is exactly the sum of root diameters; taking the least over all arrangements is optimal.
Watch out. Equality is allowed when fitting. Wall thickness is subtracted twice. A cup cannot directly hold two other cups in the nesting model.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int diameter[3],wall[3];
for(int i=0;i<3;i++){
cin>>diameter[i]>>wall[i];
}
int answer=diameter[0]+diameter[1]+diameter[2];
// Parent 3 means that this cup remains outside every other cup.
for(int mask=0;mask<64;mask++){
int value=mask;
int children[3]={};
int width=0;
bool valid=true;
for(int cup=0;cup<3;cup++){
int parent=value%4;
value/=4;
if(parent==3){
width+=diameter[cup];
}
else{
children[parent]++;
if(parent==cup||children[parent]>1||
diameter[cup]>diameter[parent]-2*wall[parent]){
valid=false;
}
}
}
if(valid){
answer=min(answer,width);
}
}
cout<<answer<<'\n';
}