776. Groups That Keep Getting Bigger

There are n kinds of token, numbered 1 to n. Kind i may be used at most lim[i] times in total.

You want to build a sequence of groups with two rules:

• within a single group every token is a DIFFERENT kind, so a group of size t uses t
• distinct kinds;
• the groups get strictly larger: group 1 is smaller than group 2, which is smaller than
• group 3, and so on.

Print the largest number of groups that can be built. Tokens may be left unused.

lim = 1 2 5 answer 3 sizes 1, 2, 3 lim = 2 1 answer 2 sizes 1 and 2 lim = 1 1 1 1 answer 2 sizes 1 and 2; sizes 1, 2, 3 would need six tokens lim = 1 1 5 5 answer 3 NOT 4, even though four groups would fit the token budget

## Reduce to the smallest possible sizes

If g groups exist at all, then g groups of sizes exactly 1, 2, ..., g exist. Sizes are strictly increasing whole numbers, so the j-th is at least j; shrinking each group down to size j by discarding tokens keeps every kind distinct within the group, keeps the sizes strictly increasing, and only frees up allowance. So from here on the sizes are fixed and the only question is whether the kinds can cover them.

## The condition that looks right and is not

A kind can appear at most once per group, so across g groups kind i is usable at most min(lim[i], g) times. The g groups need 1 + 2 + ... + g = g(g + 1) / 2 tokens. So surely

sum over i of min(lim[i], g) >= g(g + 1) / 2

is the test. It is necessary. It is NOT sufficient, and lim = 1 1 5 5 is the counterexample: at g = 4 the left side is 1 + 1 + 4 + 4 = 10 and the right side is 10, so the condition passes. But the group of size 4 must use all four kinds, exhausting both kinds with allowance 1, and the group of size 3 is then left with only two usable kinds. The real answer is 3.

Counting total supply against total demand is not enough when the demand is spread across groups that each refuse repeats. That is the trap this problem exists for.

## The condition that is right

Check every prefix of the group sizes, largest first. Take the t largest groups, whose sizes are g, g - 1, ..., g - t + 1. Together they need

t * g - t(t - 1) / 2

tokens, and no kind can contribute more than t of them, because it appears at most once in each of those t groups. So the supply available to those t groups is sum over i of min(lim[i], t), and we need

for every t from 1 to g: t * g - t(t - 1) / 2 <= sum over i of min(lim[i], t)

Taking t = g recovers the naive condition, so this is strictly stronger; on 1 1 5 5 with g = 4 the case t = 2 demands 2 * 4 - 1 = 7 and supplies only 1 + 1 + 2 + 2 = 6, which is exactly the failure the naive count missed.

## Why the condition is also sufficient

Necessity is the counting argument just given. Sufficiency is the bipartite degree theorem of Gale and Ryser: a set of demands on one side can be met from capacities on the other side, with at most one edge between any pair, exactly when for every t the t largest demands are covered by sum of min(capacity, t). Here the demands are the group sizes and the capacities are min(lim[i], g), and since t <= g we have min(min(lim[i], g), t) = min(lim[i], t), which is why the formula above mentions g only on the demand side.

The construction behind it is the natural one: fill the groups from largest to smallest, and in each group take the kinds with the most allowance still remaining. Checking the condition is all the code has to do.

## Why the predicate is monotone

Suppose g groups are possible. Then g - 1 are: delete the largest group. Concretely, the condition for g - 1 asks t(g - 1) - t(t - 1) / 2 <= f(t) for t <= g - 1, and the left side is smaller than the one already known to hold for g. So the feasible group counts form a prefix 0 .. answer, and the answer is the LAST true value, which means the midpoint rounds UP.

## The bounds

lo = 0 and hi = n. There can never be more than n groups, because the largest group has size g and needs g distinct kinds, and only n kinds exist. Notice that hi does not depend on the allowances at all, which is why a single enormous allowance does not help: one kind usable a billion times still yields exactly one group, because a second group would need a second kind.

## Computing the check in one pass

Sort the allowances ascending and take prefix sums. Then

f(t) = sum over i of min(lim[i], t) = prefix[j] + t * (n - j)

where j is the number of allowances strictly below t. As t runs from 1 to g, j only moves forward, so one pointer carries it and the whole check costs O(n).

## The boundary that breaks a careless implementation

t(t - 1) / 2 must use the integer halving of t(t - 1), which is always even, so no rounding question arises. Writing t * (t - 1) / 2 is safe; writing t / 2 * (t - 1) is not, because the division happens first and truncates on odd t.

And the pointer j must be reset at the start of each feasibility check, since each check restarts t from 1. Carrying it between probes is a subtle and very quiet bug.

## Relationship with problem 769

769 offers exactly the same mistake. The tempting test there is one global figure, the total divided by the number of workers, and it is wrong; the correct test is P[i] <= m * i for EVERY prefix i. The tempting test here is the one global figure sum of min(lim[i], g) >= g(g + 1) / 2, and the correct one runs over every t from 1 to g.

In both, the global version is necessary and not sufficient, because a total says nothing about how the demand is spread: 769's sacks cannot travel rightwards, and these groups cannot repeat a kind. When a feasibility test is a single sum, the question to ask is which part of the data could still be starved while the sum looks healthy.

## Overflow

t * g reaches n * n = 10^10, and the demand t * g - t(t - 1) / 2 reaches 5000050000 at t = g = 10^5. The supply f(t) = prefix[j] + t * (n - j) is bounded by n * t and so reaches 10^10 as well, because every allowance folded into prefix[j] is smaller than t, which is itself at most n. The prefix array is built from the raw allowances, though, so it reaches n * max(lim) = 10^5 * 10^9 = 10^14 on its own.

All of those need 64 bits, and the threshold is lower than it looks: n * n passes INT_MAX at n = 46341, where it is 2147488281 against 2147483647. One kind of token past that point and a 32-bit version starts reporting a smaller answer than the truth.

## Cost

O(n log n) to sort, then O(n) per check over O(log n) checks.

Constraints - `1 ≤ n ≤ 100000` - `1 ≤ lim[i] ≤ 10^9`