sums[mask] = sums[mask ^ lsb] + times[lsb.bitlength() - 1]
The solver combines binary search over candidate makespans (the optimal makespan is always the load of some worker, i.e., a subset sum, so candidates = distinct subset sums) with a bitmask-DP feasibility check: dp[mask] = minimum number of workers needed to process the jobs in mask, where a worker may take any sub-subset whose sum ≤ bound M. A packing exists iff dp[full] ≤ K. Subset sums are precomputed once; dp values are capped at K+1 (only "≤ K" matters) and the submask search early-exits at 2 workers (the optimum for any mask that doesn't fit one worker).
def min_makespan(times, K):
times = list(times)
N = len(times)
if N == 0: return 0
if K <= 1: return sum(times)
if K >= N: return max(times)
size = 1 << N
full = size - 1
K1 = K + 1 # cap: we only care whether dp <= K
# subset sums, computed once outside the binary search
sums = [0] * size
for mask in range(1, size):
lsb = mask & -mask
sums[mask] = sums[mask ^ lsb] + times[lsb.bit_length() - 1]
# answer is always the load of the bottleneck worker => a subset sum
candidates = sorted(set(sums[1:]))
def feasible(M):
dp = [0] * size
dp[0] = 0
for mask in range(1, size):
if sums[mask] <= M: # whole mask fits one worker
dp[mask] = 1
continue
best = K1
sub = (mask - 1) & mask # proper non-empty submasks
while sub:
if sums[sub] <= M:
v = dp[mask ^ sub] + 1 # pack `sub` on one worker,
if v < best: # rest was already solved
best = v
if best == 2: # cannot do better here
break
sub = (sub - 1) & mask
dp[mask] = best
return dp[full] <= K
lo, hi = 0, len(candidates) - 1
while lo < hi:
mid = (lo + hi) // 2
if feasible(candidates[mid]): hi = mid
else: lo = mid + 1
return candidates[lo]
Why this matches the requested approach: dp[mask] is exactly "is this subset packable into the remaining workers" — a sub-subset sub is removed onto one worker, and the rest mask ^ sub is checked against the already-computed worker count. Since mask ^ sub < mask numerically, the DP proceeds in a single increasing pass (O(3^N) worst case per check, ~531k submask visits at N=12; with early exit it's far less). Complexity: O(3^N · log 2^N) ≈ 6M simple ops for the full problem — ~0.13 s measured. An optional reconstruct() walks the same dp table to emit the actual worker loads for a given bound.
Verified in Python 3 (ran on 3.14; target 3.11-compatible, stdlib only): **1. Hand-crafted edge cases (11)** — all passed: N=1 with any K; K=1 (answer = total); K ≥ N (answer = max); all-equal jobs `[1000]*12, K=4 → 3000`; `[4,7,8], K=2 → 11`; `[99,100,101], K=2 → 199`; six 3s + six 2s with K=4 → **8** (7 is infeasible: `(3,2,2)×3` leaves `(3,3),(3)` = 5 workers; `(3,3,2)×3 + (2,2,2)` = 8). Note: my first draft of two expected values was wrong; the solver (matching brute force) proved them wrong and the corrected values were re-verified. **2. Brute-force differential testing (760 random cases)** — exhaustive `K^N` enumeration compared against the solver: 400 cases with N∈[1,8], K∈[1,4], times∈[1,50]; 300 structured cases with few distinct values (ties/stress); 60 cases with N∈[1,10], times∈[1,1000]. Zero mismatches. **3. N=12 large-instance validation (60 checks)** — for 5 adversarial time vectors × 4 values of K plus 40 random N=12 instances: `reconstruct()` produced valid packings (≤ K workers, every load ≤ M, sum conserved), and a **fully independent feasibility routine** (reachable-mask sets per worker, different DP structure) confirmed both feasibility at M and infeasibility of every smaller candidate — i.e., the solver's answer is minimal. All passed. **4. Timing** — worst-case adversarial N=12, K=4 (`[1000..989]`): solves in ~0.13 s per call; 40 full N=12 minimality checks took ~16 s total including the independent checker. **Result: 831 tests, 0 failures.**
{"model": "deepseek-v4-flash", "problem_class": "parallel-job-makespan-partition", "result": "passed", "tests": 831}