769. Passing Sacks Down the Line

n workers stand in a line, numbered 1 to n from left to right. Worker i is holding a[i] sacks. In one move you pick any worker i with i >= 2 who is holding at least one sack, and that worker passes ONE sack to the worker immediately on their left. Sacks never travel to the right, and a worker's count never goes negative.

You may make as many moves as you like. Print the smallest possible value of the largest number of sacks any single worker ends up holding.

a = 3 7 1 answer 5 two sacks move left from worker 2, giving 5 5 1 a = 10 1 1 1 answer 10 worker 1 can never give anything away a = 0 0 0 0 10 answer 2 the ten spreads across all five workers a = 42 answer 42 one worker, no moves possible

## Why simulating moves gets nowhere

The state space is every arrangement with the same total, which is astronomically large, and there is no obvious rule for which move to make next. Greedily moving a sack from the current maximum can even be counterproductive when the maximum is worker 1, who has nobody to pass to.

Ask about the outcome instead: can the largest holding be held down to m?

## What the moves can and cannot do

Sacks only travel LEFT. That single fact determines everything.

Look at the first i workers as a group. A move inside the group changes nothing about the group's total. A move from worker i + 1 to worker i ADDS to the group's total. No move ever removes anything from the group, because that would require a sack crossing from worker i to worker i + 1.

So for every i, the total held by the first i workers can only grow. Write P[i] for the starting total a[1] + ... + a[i].

## The feasibility test

If the largest holding is to be at most m, then the first i workers together hold at most m * i. Since their total never drops below P[i], we need

P[i] <= m * i for every i from 1 to n

That condition is also SUFFICIENT, which is the half worth proving. Build a target arrangement by sweeping from the RIGHT: each worker keeps at most m and pushes everything else left.

Write out(i) for the number of sacks the block i .. n pushes out past its left end. Worker i receives out(i + 1) from the right, keeps at most m, and sends the rest on, so

out(n + 1) = 0 out(i) = max(0, a[i] + out(i + 1) - m)

Unrolling that recurrence down to i = 1 gives

out(1) = max(0, the largest value of P[j] - m * j over j from 1 to n)

which reads exactly as it should: the block 1 .. j starts with P[j] sacks and has room for m * j, so anything beyond that has to spill. The prefix condition says every one of those terms is at most zero, so out(1) is 0. Nothing spills past worker 1, every worker finishes holding m or fewer, and every move the sweep performed sent a sack leftwards from a worker who had one, so all of them are legal.

The check itself is one pass:

run = 0 for i in 0 .. n - 1: run += a[i] if run > m * (i + 1): return false return true

## Why the predicate is monotone

If every prefix satisfies P[i] <= m * i then it satisfies P[i] <= (m + 1) * i as well, since i >= 1. So feasibility survives every increase of m and the answer is the FIRST true value.

## The bounds

lo = a[1], the first worker's starting count. Worker 1 never gives anything away and only ever receives, so the answer can never be below a[1]. This is the bound that teaches the problem: it is not min(a) and it is not 0, and an input like 10 1 1 1 exists precisely to make that point.

hi = max(a), achieved by making no moves at all.

## The boundary that breaks a careless implementation

The answer is a CEILING, not a floor. On 1 2 3 4 the total is 10 across 4 workers, and the answer is 3, not 2. Anyone who reasons "the answer is the average" and writes total / n is wrong on every input whose total is not divisible; anyone who writes the maximum of ceil(P[i] / i) directly is right, and the binary search is the version of that which does not have to think about rounding at all.

The other trap is comparing run > m * i with i taken as the 0-based index. The first worker is i = 1 in the formula, so a 0-based loop must use i + 1. Off by one here makes the test reject every m and the search return max(a).

## Relationship with problem 767

767 asks for the same thing, the smallest achievable value of the largest pile, and tests a candidate m with one pass over the input. There the piles are independent: a bag of a[i] marbles needs ceil(a[i] / m) bags no matter what happens to its neighbours, so the check is a sum of per-element terms compared against the operation budget.

Here the piles are coupled by position, because a sack only ever moves LEFT. That is why the check is not per element but per PREFIX, P[i] <= m * i, and why worker 1 puts a floor under the answer that no amount of rearranging can lower.

## Overflow

P[n] reaches 2 * 10^5 * 10^9 = 2 * 10^14, and m * i reaches the same. Both sides of the comparison must be 64-bit. In 32 bits the products wrap, the comparison flips, and the search returns a number far below the truth, which looks like a better answer rather than a bug.

## Cost

Time O(n log(max a)). Space O(1) beyond the input.

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