The Fewest Groups With No Argument
n people are given, along with m pairs who argue with each other. Split everyone into
groups so that no group contains a pair who argue. Print the fewest groups needed.
4 people in a cycle 1-2 2-3 3-4 4-1 -> 2
3 people who all argue -> 3
5 people, nobody argues -> 1
## The same partition as 591, with a different cost
Replace 591's group cost with a constant 1 and the legality test with "this group contains no arguing pair", and the recurrence is identical:
ok[mask] = no two people in mask argue
dp[mask] = fewest groups covering exactly the people in mask
dp[0] = 0
dp[mask | s] = min(dp[mask | s], dp[mask] + 1) for legal s in the complement
Groups here have no fixed size, so every conflict-free subset is a candidate.
## Computing ok[mask] in one pass
Testing every pair inside every mask is O(2^n * n^2). Build it incrementally instead:
ok[0] = true
let low = the lowest set bit of mask, at index i
ok[mask] = ok[mask without low] and (adj[i] & (mask without low)) == 0
Removing the lowest person leaves a smaller mask already known to be conflict-free or not, and the only new pairs are that person against the rest. One bitwise AND settles them all.
## The lowest-free rule, once more
Require s to contain the lowest unused person. Without it the table finds each partition
once per ordering of its groups, which at n = 14 is the difference between finishing and not.
## Why the answer is never more than needed
This is graph colouring, and the number printed is the chromatic number. Two facts make good
free checks: a graph with no edges answers 1, and a clique on n people answers n, since
every pair argues and no two can share a group. Both are in the tests.
## Recursion or loops
The recurrence is a natural recursion over masks with memoisation, and a natural upward loop. Both are correct, because every transition moves to a strictly larger mask, so the loop order is already a valid topological order.
The loop is preferred here only because 3^14 function calls carry real overhead in most
languages. When the reachable part of the table is sparse, memoisation is the better choice, and
that trade is what the two forms are really about.
## Cost
Time O(2^n * n) for the legality table plus O(3^n) for the partition. Space O(2^n).