764. Breaking the Bar Fairly

A chocolate bar is a row of n squares, square i worth a[i] points of sweetness. You must snap it into exactly k CONTIGUOUS non-empty pieces and hand one piece to each of k people. Every square goes to somebody, and the order of the squares cannot change.

Whoever receives the least sweetness decides how good the split was. Print the largest value that share can be made.

If k is greater than n there is no way to give everyone a piece, so print -1.

a = 5 1 3 4 2 6, k = 3 answer 6 pieces 5+1, 3+4, 2+6 score 6, 7, 8 a = 7 2 9 1, k = 1 answer 19 one person takes the whole bar a = 4 9 2 7 3, k = 5 answer 2 a square each, so the smallest square wins a = 1 2 3, k = 4 answer -1 more people than squares

## Read problem 260 first, then read this line twice

Problem #260 splits an array into k contiguous parts and asks for the SMALLEST possible value of the LARGEST part. This problem splits an array into k contiguous parts and asks for the LARGEST possible value of the SMALLEST part.

They are not the same question and they do not have the same answer. On 5 1 3 4 2 6 with k = 3, #260 answers 8 and this one answers 6. Every piece of machinery flips:

#260 this problem objective minimise the maximum maximise the minimum predicate "at most k pieces" "at least k pieces" feasible region large values work small values work midpoint rounds down up lower bound the largest square the smallest square upper bound the total the total divided by k

Solving one and pattern-matching the other is the single most common way to lose an interview on this family. The two are placed side by side on purpose.

## Why you cannot just compute it

An even split does not exist in general, and cutting the bar into pieces of equal LENGTH is not the answer either. On 1 1 1 1 1 1 1 9 with k = 2, halving by position gives 1 1 1 1 and 1 1 1 9, which scores 4, while the correct cut takes the seven ones together against the nine and scores 7.

Trying every set of cut positions costs C(n - 1, k - 1). For n = 40 and k = 20 that is C(39, 19) = 68923264410, about seventy billion, more than twenty times the number of seconds in a century.

## Testing a candidate is easy

Ask instead: can every person be given at least m? Walk the squares left to right, accumulating. The moment the running total reaches m, close that piece and start the next from zero:

count = 0, cur = 0 for x in a: cur += x if cur >= m: count += 1 cur = 0 feasible(m) = (count >= k)

Anything left over at the end is simply attached to the last closed piece, which already has at least m, so it never hurts.

## Why closing a piece as early as possible is optimal

This is the part to argue rather than assume.

Suppose some valid split into k pieces exists where every piece is worth at least m. Let its first cut be after position j. The greedy closes its first piece after position g, where g is the earliest position whose prefix reaches m. Since the valid split's first piece also reaches m, we get g <= j.

Now move the valid split's first cut back from j to g. Piece one still holds at least m, by the definition of g. Piece two only GAINS the squares between g and j, and since every square is positive it cannot drop below m either. So the modified split is still valid.

Repeat the argument on the remaining suffix. Piece by piece, any valid split can be pushed into the greedy's cuts without ever becoming invalid. So if a valid split exists, the greedy finds one, which is exactly what "the greedy count is correct" means.

The argument uses positivity. Squares are worth at least 1, which is why the constraints say so.

## Why the predicate is monotone

If every person can be given at least m, then every person has also been given at least m - 1, using the very same cuts. So feasibility never turns back on as m grows: the true values form a prefix 0, 1, ..., answer and the false values a suffix. Binary search finds the last true.

## The bounds, and why they are those

lo = min(a). Every piece is a non-empty run of positive values, so no piece can be worth less than the smallest single square. And with k <= n there is always a split scoring at least that much: give one square to each of the first k - 1 people and the rest to the last.

hi = total / k, integer division. The k pieces sum to total, so the smallest of them is at most the average, and the answer is an integer so the floor is safe. Using total itself as the upper bound is not wrong, only wasteful, and it is a good habit to bound tightly enough that the bound itself explains the problem.

## The boundary that breaks a careless implementation

Because this searches for the LAST true value, the midpoint must round UP:

mid = lo + (hi - lo + 1) / 2 if feasible(mid): lo = mid else: hi = mid - 1

Round down and the case hi == lo + 1 computes mid == lo, which is feasible, which sets lo = mid = lo, and the loop never moves again. That is an infinite loop, not a wrong answer, and it only appears once the range has narrowed to two, so small hand-traced examples pass. Problem #259 makes the same point; #251 and #260 round the other way.

## Overflow

2 * 10^5 squares worth 10^9 each total 2 * 10^14. The running accumulator, the total and the upper bound all exceed a 32-bit integer, and a wrapped total makes hi negative, so the loop exits immediately and prints min(a). Use 64-bit everywhere.

## Cost

Sorting is not needed; the order is fixed. Time O(n log(total / k)), space O(1) beyond the input.

Constraints - `1 ≤ n ≤ 200000` - `1 ≤ k ≤ 200000` - `1 ≤ a[i] ≤ 10^9`