588. Sharing the Work as Evenly as Possible
n jobs, each with a duration, are to be handed out to k workers. Every job goes to exactly
one worker, and a worker who receives no job is allowed. All workers start at the same moment
and work in parallel, so everything is finished when the BUSIEST worker finishes.
Print the smallest possible finishing time.
4 jobs 3 1 4 2, k = 2 -> 5 {3,2} and {1,4}
4 jobs 1 2 3 4, k = 1 -> 10 one worker does everything
## Why sorting and dealing does not work
Handing the longest remaining job to the least loaded worker is a good heuristic and it is not
optimal. On 5 5 4 4 3 3 2 with k = 3 it gives 10 and the answer is 9.
## The state
dp[w][mask] = the smallest possible finishing time when the jobs in mask
have been handed to the first w workers
dp[0][0] = 0
dp[w][mask] = min over subsets s of mask of max(dp[w-1][mask \ s], sum(s))
s is what worker w takes. The max is because the finishing time is the busiest worker,
not the total.
The answer is dp[k][full].
## Enumerating the subsets of a mask
The inner loop is over SUBSETS of mask, and the standard idiom is:
s = mask
while true:
... use s ...
if s == 0: break
s = (s - 1) & mask
(s - 1) & mask steps to the next smaller subset of mask and nothing else, which is why the
idiom is written exactly this way. Starting from mask and stopping after s = 0 visits every
subset including the empty one, once each.
## Why this is 3^n and not 4^n
Summed over all mask, the number of (mask, subset) pairs is not 2^n times 2^n. Each of
the n items is in one of THREE states: outside mask, in mask but not in s, or in both.
So the total is exactly 3^n.
At n = 12 that is 531441 rather than 16 million, and knowing which of the two a loop costs is
the difference between a solution that runs and one that does not.
## Precomputing the sums
sum(s) is needed for every subset, so compute it once for all 2^n masks with
sum[mask] = sum[mask without its lowest bit] + a[index of that bit]
Recomputing it inside the subset loop turns 3^n into 3^n * n for no reason.
## Boundaries
With k = 1 the answer is the total. With k >= n the answer is the single largest job, since
every job can have its own worker. Both are in the tests.
## Cost
Time O(k * 3^n). Space O(2^n).
Constraints - `1 ≤ n ≤ 12` - `1 ≤ k ≤ 12` - `1 ≤ each duration ≤ 10^6`
Input
The first line contains two integers n and k.
The second line contains n integers, the job durations.
Output
Print one integer, the smallest possible finishing time.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.