Balancing Watermelons
Autumn Tournament (2018)
Submission name: dini.cpp
Problem summary
Distribute four watermelons between two hands to minimize the absolute difference between the total weights in the hands. A hand may hold any number of watermelons.
Input
Four integer watermelon weights.
Output
The smallest possible nonnegative weight difference.
Constraints
0 ≤ each weight < 100. The prose describes positive weights, while the printed bounds also allow zero.
Worked example
First official statement sample.
Input
4 7 2 8
Output
1
Solution analysis
- Choose the watermelons for the left hand; all remaining ones go in the right hand. Four binary choices give 16 subsets.
- If the total weight is total and the chosen subset weighs left, the other hand weighs total − left. Their difference is abs(total − 2 × left). Minimize it over all subsets.
- For 4, 7, 2, 8, choose 4 and 7 for one hand and 2 and 8 for the other. The weights are 11 and 10, giving difference 1. Three-versus-one distributions must also be considered.
Why it works
Every assignment to the hands corresponds to a subset of the four items for the left hand. The loop examines every subset and computes its exact imbalance. Its minimum is therefore the smallest achievable imbalance.
Watch out. Do not require two watermelons per hand. Handle zero weights as permitted by the printed constraints.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every assignment to the hands corresponds to a subset of the four items for the left hand.
// The loop examines every subset and computes its exact imbalance.
#include<algorithm>
#include<array>
#include<cstdlib>
#include<iostream>
using namespace std;
int main(){
array<int,4>weight;
int total=0;
for(int&value:weight){
cin>>value;
total+=value;
}
int best=total;
for(int mask=0;mask<16;++mask){
int left=0;
for(int i=0;i<4;++i){
if((mask&(1<<i))!=0){
left+=weight[i];
}
}
best=min(best,abs(total-2*left));
}
cout<<best<<'\n';
}