741. Three Pieces In Increasing Weight
Cut the array into THREE non empty contiguous pieces, left, middle and right. Count the cuts for which
total(left) <= total(middle) <= total(right)
All values are non negative.
1 1 1 -> 1
1 2 2 2 5 0 -> 3
3 2 1 -> 0
0 0 0 0 -> 3
## Fix the first cut, then count the second
Write P for the prefix sums and let the first cut be after index i, so the left piece
totals P[i]. Let the second cut be after index j. Then the middle totals P[j] - P[i] and
the right totals P[n] - P[j].
The two conditions become bounds on P[j] alone:
left <= middle => P[j] - P[i] >= P[i] => P[j] >= 2 P[i]
middle <= right => P[n] - P[j] >= P[j] - P[i] => 2 P[j] <= P[n] + P[i]
So for each i, the valid j form a contiguous RANGE of prefix values. That is the whole
problem: two awkward-looking inequalities both turn into bounds on the same quantity.
## Why the range can be found by binary search
The values are non negative, so P is non decreasing. A non decreasing array lets both bounds
be located with a binary search, and the count is the difference of the two positions.
If negatives were allowed, P would not be sorted, the bounds would no longer describe a
contiguous range of indices, and this method would collapse. The constraint is doing real work
and the statement says so for that reason.
## The two pointers alternative
Both bounds move right as i increases, since 2 P[i] grows and P[n] + P[i] grows. So two
pointers can sweep instead of binary searching, giving O(n) rather than O(n log n). Either
is fast enough here; noticing the monotonicity is the point.
## The range must stay inside i+1 .. n-1
The middle and right pieces must both be non empty, so j runs from i + 1 to n - 1. A
search over the whole prefix array silently allows an empty middle or an empty right piece.
3 2 1 answering 0 is the check: P = 0 3 5 6, and the only candidate cut has a left piece
already heavier than anything that can follow.
## Why all zeros gives 3
With every total 0 the conditions read 0 <= 0 <= 0, which always holds, so every choice of
two cuts counts. For n = 4 the two cuts are chosen from the 3 interior positions, and
3 choose 2 is 3.
## Overflow
The SUMS are comfortable. 10^5 values of 10^4 cap P[n] at 10^9, so 2 P[i] and
P[n] + P[i] both cap at 2 * 10^9, and 2000000000 is below INT_MAX = 2147483647.
Every sum in this problem fits in a signed 32 bit integer.
The COUNT is what does not. Every pair of interior cut positions can qualify, and with
n = 100000 that is 99999 choose 2 = 4999850001, about 5 * 10^9. So the accumulator
needs 64 bits even though nothing it accumulates does.
## Cost
Time O(n log n) with binary search, or O(n) with two pointers. Space O(n).
Constraints - `3 ≤ n ≤ 100000` - `0 ≤ each value ≤ 10^4`
Input
The first line contains an integer n.
The second line contains n non negative integers.
Output
Print one integer, the number of qualifying pairs of cuts.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.