743. Four Pieces With Three Cuts Thrown Away
Choose three indices i < j < k and discard the values AT those three positions. That leaves
four pieces:
a[0 .. i-1] a[i+1 .. j-1] a[j+1 .. k-1] a[k+1 .. n-1]
Print yes if the three indices can be chosen so all four pieces have EQUAL totals and none of
them is empty, and no otherwise.
1 2 1 2 1 2 1 -> yes cuts at 1, 3, 5 leave 1 | 1 | 1 | 1
1 2 1 2 1 4 1 -> yes
0 0 0 0 0 0 0 -> yes
1 -> no
## Why a triple loop is too slow and a double loop is not
Trying every i, j, k is O(n^3). The way through is to fix the MIDDLE cut j first,
and then handle the left and right halves independently, because once j is fixed the two
halves share nothing.
Fixing the middle element of a symmetric structure, so that two independent searches fall out,
is the idea here. It turns O(n^3) into O(n^2).
## For a fixed middle cut
With j fixed, scan i from 1 up to j - 2 and collect every total P[i] for which
piece1 == piece2 that is P[i] == P[j] - P[i+1]
into a set. Then scan k from j + 2 to n - 2 and check whether
piece3 == piece4 that is P[k] - P[j+1] == P[n] - P[k+1]
and whether that shared value is in the set. If so, all four match and the answer is yes.
## The index arithmetic is where this goes wrong
Every piece excludes its bounding cut, so the totals are
P[i], P[j] - P[i+1], P[k] - P[j+1] and P[n] - P[k+1], with the +1 in three of the
four. Dropping one of them produces a method that is correct on symmetric inputs and wrong
elsewhere, which is the hardest kind of error to see.
## The gaps between the cuts
Each piece must be non empty, so the cuts need room: i >= 1, j >= i + 2, k >= j + 2 and
k <= n - 2. That also means n must be at least 7 for any answer to exist, and a shorter
array can be rejected immediately.
## Why all zeros answers yes
With every total 0 all four pieces match automatically, and n = 7 leaves exactly enough room.
It is the cheapest check that the gap arithmetic is right, because it fails the moment any of
the four bounds is off by one.
## Overflow
3000 values of magnitude 10^9 total 3 * 10^12, so the prefix sums and every piece total
need 64 bits.
## Cost
Time O(n^2). Space O(n).
Constraints - `1 ≤ n ≤ 3000` - `-10^9 ≤ each value ≤ 10^9`
Input
The first line contains an integer n.
The second line contains n integers, which may be negative.
Output
Print one word on one line: yes if such a choice exists, otherwise no.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.