Assign the Builders
National Olympiad — National round
Submission name: builders.cpp
Problem summary
Assign N companies bijectively to N jobs. Company i succeeds on job j with the supplied probability. The probability of completing the entire project is the product of the assigned probabilities. Maximize this product.
Input
N, then an N×N table of integer percentages.
Output
The maximum project-success probability as a percentage, rounded to six decimal places.
Constraints
1 ≤ N ≤ 20; percentages from 0 through 100.
Worked example
An independently prepared example for this explanation.
Input
2 80 20 10 90
Output
72.000000
Solution analysis
- Let dp[mask] be the largest product for assigning the first popcount(mask) companies to the jobs in mask.
- Assign the next company to any unused job and update the enlarged mask.
- Start with product one for the empty assignment, then multiply the final probability by 100.
Why it works
Every bijection has a unique last assignment relative to company order. The recurrence checks every last job and retains the best product.
Watch out. Probabilities multiply, not add. Zero-probability assignments remain valid.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Every bijection has a unique last assignment relative to company order. The recurrence
// checks every last job and retains the best product.
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
using namespace std;
int main(){
int n;
cin>>n;
vector<vector<double>>p(n,vector<double>(n));
for(auto&r:p){
for(double&x:r){
cin>>x;
x/=100;
}
}
vector<double>d(1<<n);
d[0]=1;
for(int mask=0;mask<(1<<n)-1;mask++){
int i=__builtin_popcount((unsigned)mask);
for(int j=0;j<n;j++){
if(!(mask>>j&1)){
d[mask|1<<j]=max(d[mask|1<<j],d[mask]*p[i][j]);
}
}
}
cout<<fixed<<setprecision(6)<<100*d.back()<<'\n';
}