1199. The Smallest Largest Group, and How Many Reach It

Each of n items carries a positive weight. Over every way to put the items into exactly k non-empty groups, let the COST of a split be the weight of its heaviest group. Report the smallest cost any split achieves, and how many splits achieve it.

weights 1 2 3 4, k = 2 all seven two-group splits 1 1 1 2 -> groups weigh 6 and 4, cost 6 1 1 2 1 -> 7 and 3, cost 7 1 1 2 2 -> 3 and 7, cost 7 1 2 1 1 -> 8 and 2, cost 8 1 2 1 2 -> 4 and 6, cost 6 1 2 2 1 -> 5 and 5, cost 5 <- best 1 2 2 2 -> 1 and 9, cost 9 smallest cost 5, achieved by one split

## What most people try first

Enumerate every split into k groups, compute each cost, and keep the minimum. That is correct and it does S(n, k) units of work no matter how early the answer becomes obvious. At n = 8, k = 4 it is 1701 splits, at n = 12 more than a million, and the great majority of them are already worse than something found in the first few seconds.

The second half of the question is the part that catches people out. Having found the smallest cost, it is tempting to run the enumeration again to count the splits that achieve it. That doubles the work and, worse, it invites a bounded second pass that is no longer safe, because a bound tuned to find one optimum can legitimately skip others that tie with it.

## The method, and the one subtlety in it

Carry best, the smallest cost seen so far, and ties, how many splits have achieved it. Start best at the total of all the weights, which is the cost of the one-group split and therefore an upper bound on the answer.

go(i, used, sum[]): if i == n: if used != k: return c = max(sum[1..used]) if c < best: best = c; ties = 1 elif c == best: ties += 1 return if used > k or used + (n - i) < k: return for lab in 1 .. min(used + 1, k): if sum[lab] + w[i] > best: continue # cannot tie, let alone beat sum[lab] += w[i]; go(i + 1, max(used, lab)); sum[lab] -= w[i]

The bound is > and not >=, and that single character is the whole problem. A branch whose group would reach exactly best can still produce a split of cost exactly best, and such splits must be counted. Writing >= prunes them away and the reported cost stays right while the tie count comes out too small, which is the kind of bug that passes every test where the optimum is unique. The 4 2 and 4 4 tests have a unique optimum and would not catch it; the 6 3 test, with fifteen splits tied at cost 2, is there to catch it.

## Why it is correct

Weights are positive, so a group's weight only rises and the cost of a split is at least the weight of any group in any prefix of it. If a group in the prefix already weighs more than best, every completion has cost above best, so none of them can beat or tie the incumbent and skipping them loses nothing. When best improves, ties is reset to 1, which is right because every split counted before had a strictly larger cost and is no longer optimal. Splits pruned under an older, larger best had cost above that older value, hence above the new one too, so they were never optimal either and their loss does not affect the count.

## Overflow

With n at most 10 and weights at most 100 the total is at most 1000, so nothing here comes close to INT_MAX = 2147483647 and a 32-bit integer is ample. The count of ties is bounded by S(10, 5) = 42525, also small. This is stated so the absence of a 64-bit type is a decision rather than an oversight.

## Cost

One node per prefix the bound admits, which depends on the order the weights arrive in and on how quickly a good incumbent is found. Worst case it is the full S(n, k) walk, and the bound never makes it slower, since a skipped branch is strictly cheaper than an explored one.

Constraints - `1 ≤ k ≤ n ≤ 10` - `1 ≤ w[i] ≤ 100`