1764. The Biggest Shortfall

There are nl workers and nr shifts, and m lines each say that a worker is willing to take a shift. For a SET of workers A, write N(A) for all the shifts that at least one worker in A is willing to take. The SHORTFALL of A is size(A) - size(N(A)), which is how many workers of A cannot possibly be placed no matter how the rest is arranged.

Print the largest shortfall over all sets of workers, or 0 if no set has a positive one.

willing: 1-1, 2-1, 3-1, 4-2 -> 2

Workers 1, 2 and 3 between them are willing to take only shift 1, so that set of size 3 has N of size 1 and a shortfall of 2. No set does worse.

## Why anyone cares, and the name

A shortfall of 0 everywhere says every set of workers between them can reach at least as many shifts as it has members, and HALL'S THEOREM says that is exactly the condition for every worker to get a shift. So this number is the amount by which Hall's condition is violated, and printing 0 is the same as saying "all workers can be placed".

The theorem is not obvious in the direction that matters. One direction is: if some set of k workers can reach only j < k shifts then at least k - j of them are stuck, since the j shifts hold at most j people. The other direction, that no violation implies everyone is placeable, is the content.

## What most people try first

Enumerate every set of workers. That is exactly the definition, and 2^300 sets is beyond counting. This problem's oracle does precisely this, on at most six workers, which is how the method below was checked.

The second attempt is to look only at SINGLE workers, reporting 1 for each worker with no willing shift. That misses the example above entirely, where every worker has a shift available and three of them share one. Checking pairs as well still misses a conflict among three.

## The method

answer = nl - (the largest number of shifts that can be filled)

Compute the largest number of shifts that can be filled, exactly as problem 1763 does with a flow or problem 1786 does with augmenting paths, and subtract it from nl.

## Why those are the same number

Call the largest number of filled shifts f and the largest shortfall d.

d >= nl - f: the proof is a minimum cut. Take the cheapest split of problem 1763's network. Let A be the workers on the sink side of it. For a worker in A, every shift it is willing to take must be on the sink side too, or the capacity-1 pair arc would cross the split and the split would have to pay for it; a cheapest split never pays for a pair arc, because paying for the worker's single source arc instead costs the same 1 and covers everything. So N(A) sits on the sink side, and the split pays 1 for each worker NOT in A and 1 for each shift of N(A). Hence f = cut = (nl - size(A)) + size(N(A)), which rearranges to size(A) - size(N(A)) = nl - f. That set A attains the shortfall.

d <= nl - f: any set A with shortfall d leaves at least d of its members unplaced in every arrangement, so f <= nl - d.

Both ways, d = nl - f. This is the DEFECT form of Hall's theorem, and the reason it is worth proving is that it turns an exponential definition into one flow computation.

## Cost

One maximum flow, O(min(nl, nr) * (nl + nr + m)), about 1.1 * 10^6 at the limits. The answer is between 0 and nl, so at most 300, and nothing here approaches 2147483647.

Constraints - `1 ≤ nl ≤ 300` - `1 ≤ nr ≤ 300` - `0 ≤ m ≤ 3000` - `1 ≤ u ≤ nl` and `1 ≤ v ≤ nr` - the same pair may be listed more than once - a worker may have no willing shift and a shift may have no willing worker, so the graph may be disconnected