Splitting Into Groups With the Least Spread
n numbers must be split into exactly k groups, all of the SAME size n / k. Within a
group every number must be distinct. The spread of a group is its largest value minus its
smallest.
Print the smallest possible total spread over all k groups, or -1 when no legal split
exists.
4 numbers 1 2 1 4, k = 2 -> 4 {1,2} and {1,4}, spreads 1 and 3
4 numbers 5 5 5 5, k = 2 -> -1 no group of two can hold distinct values
2 numbers 7 7, k = 2 -> 0 groups of one, so distinctness is free
## Two stages, and why they are separate
Stage one prices every possible GROUP; stage two chooses k of them that fit together.
cost[mask] = max - min when popcount(mask) == n/k and the values in mask are distinct
infinity otherwise
dp[mask] = the least total spread using exactly the items in mask
dp[0] = 0
dp[mask | s] = min(dp[mask | s], dp[mask] + cost[s]) for legal groups s disjoint from mask
Separating the two stages keeps each one simple, and the same split appears in 592 with the cost replaced by a constant 1.
## The lowest-free rule again
Without it, every split is found k! times, which is slow though not wrong. Fix it the same
way as 585: require the new group s to contain the LOWEST item not yet used.
In code, with rem the complement of mask and low = rem & -rem, only consider subsets s
of rem with s & low non-zero. It is one extra test inside the submask loop.
## Enumerating subsets of the complement
s = rem
while s:
if s & low: ... use s ...
s = (s - 1) & rem
Note this version stops when s becomes 0 rather than after, because an empty group is not a
legal move here. In 588 the empty set WAS legal, and the loop there is written to include it.
Which of the two forms you want is decided by the problem, not by habit.
## Why the distinctness test belongs in stage one
It depends only on the group, so testing it once per mask costs O(2^n * size^2) and removes
it from the inner loop entirely. Checking it while combining groups would repeat the same work
across every partition that uses the group.
## Boundaries
k = 1 puts everything in one group: the answer is max - min if all values are distinct and
-1 otherwise.
k = n puts each number alone, so every spread is 0 and distinctness is automatic. The answer
is 0.
## Cost
Time O(2^n * size^2) for the group costs plus O(3^n) for the partition. Space O(2^n).