Minimum Payroll Restructuring
National Olympiad — Regional round (2019 season)
Submission name: restruct.cpp
Problem summary
Choose a rooted company tree. Each nonroot employee must accept their direct boss from their supplied list. Salaries are positive multiples of K, and a boss earns strictly more than the total salaries of their direct reports. Minimize total payroll.
Input
N K, then for each employee a count and the list of acceptable bosses.
Output
The minimum possible total payroll.
Constraints
2 ≤ N ≤ 5000; 1 ≤ K ≤ 550; at most 10,000 listed preferences in total; a solution exists.
Worked example
An independently prepared example for this explanation.
Input
4 100 1 4 3 1 3 4 2 1 2 1 3
Output
800
Solution analysis
- For a fixed tree the smallest salary of an employee is K times their subtree size: leaves earn K and each boss earns one K more than the sum of their children. The total is therefore K times the sum over employees of depth+1.
- Reverse the preference edges: from a potential boss, draw an edge to each employee accepting that boss. For each possible root, BFS finds the shortest feasible depth of every employee. A BFS parent tree realizes all these depths simultaneously.
- In the example choose employee 1 as root. Employees 2 and 3 can report directly to 1, and employee 4 can report to 3. The depth-plus-one values are 1,2,2,3, totaling 8, hence payroll 800.
Why it works
Induction on a fixed tree gives minimum salary K times subtree size. Double-counting ancestor-descendant pairs makes total payroll equal K times the sum of depth+1. Any valid tree rooted at r uses reversed preference edges, so each depth is at least its BFS distance. A BFS tree reaches every employee exactly at that lower bound; roots that cannot reach everyone are invalid. Trying every root therefore attains the global minimum.
Watch out. Reverse the input edges. The root needs no boss. Reject roots whose BFS cannot reach every employee; use 64-bit payroll arithmetic.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<iostream>
#include<limits>
#include<queue>
#include<vector>
// Algorithm: For a fixed tree the smallest salary of an employee is K times their subtree size:
// leaves earn K and each boss earns one K more than the sum of their children.
using namespace std;
int main(){
int n;
long long minimumSalary;
cin>>n>>minimumSalary;
vector<vector<int>>reports(n);
for(int employee=0;employee<n;employee++){
int count;
cin>>count;
while(count--){
int boss;
cin>>boss;
reports[boss-1].push_back(employee);
}
}
long long answer=numeric_limits<long long>::max();
for(int root=0;root<n;root++){
vector<int>distance(n,-1);
queue<int>pending;
pending.push(root);
distance[root]=0;
long long total=0;
int reached=0;
while(!pending.empty()){
int boss=pending.front();
pending.pop();
reached++;
total+=distance[boss]+1;
for(int employee:reports[boss]){
if(distance[employee]==-1){
distance[employee]=distance[boss]+1;
pending.push(employee);
}
}
}
if(reached==n){
answer=min(answer,total*minimumSalary);
}
}
cout<<answer<<'\n';
}