Two-Machine Workshop Schedule
Autumn Tournament (2017)
Submission name: workshop.cpp
Problem summary
Split indivisible jobs between two identical machines. Both machines may work in parallel and each job takes the same time on either machine. Determine whether every job can finish by deadline T.
Input
Number of test groups; for each group, T n followed by n processing times.
Output
For each group, 1 if a valid schedule exists, otherwise 0.
Constraints
At most 10 groups; 1 ≤ T ≤ 200000; 1 ≤ n ≤ 1000; 1 ≤ ti ≤ 100.
Worked example
Original statement sample.
Input
3 2 3 5 6 7 5 4 2 3 2 3 5 4 1 3 3 3
Output
0 1 0
Solution analysis
- If one machine receives jobs with total processing time x, the other receives total−x. A valid assignment therefore needs a reachable subset sum x between max(0,total−T) and min(T,total). Ordering the jobs on a single machine does not change its completion time.
- Use a bitset of reachable sums, initially containing only zero. For a job of duration t, reachable |= reachable << t adds all sums formed by assigning this job to the first machine. The old bits represent assigning it to the other machine. Since n≤1000 and t≤100, total≤100000 and one fixed-size bitset is sufficient.
- With T=5 and jobs 2,3,2,3, reachable sum 5 splits them into (2,3) and (2,3), so print 1. For 1,3,3,3, total=10 but no subset sums to 5, so print 0 even though total equals the combined capacity.
Why it works
The bitset invariant after each job is exactly the set of sums obtainable from a subset of processed jobs; taking or excluding the next job gives the shift-and-union update. Checking the stated interval is equivalent to both machine loads being at most T, so the decision is exact.
Watch out. A total duration ≤2T is necessary but not sufficient. Jobs cannot be split. Do not use an ascending scalar subset-sum loop that reuses a job multiple times.
Commented C++17 solution
An independently written complete program with standard headers.
#include<algorithm>
#include<bitset>
#include<iostream>
using namespace std;
int main(){
int groups;
cin>>groups;
while(groups--){
int deadline;
int jobs;
cin>>deadline>>jobs;
bitset<100001>reachable;
reachable[0]=true;
int total=0;
for(int job=0;job<jobs;job++){
int duration;
cin>>duration;
total+=duration;
// Shift uses the old state, so this job is used at most once.
reachable|=reachable<<duration;
}
bool possible=false;
int lower=max(0,total-deadline);
int upper=min(deadline,total);
for(int firstLoad=lower;firstLoad<=upper;firstLoad++){
if(reachable[firstLoad]){
possible=true;
break;
}
}
cout<<(possible?1:0)<<'\n';
}
}