2372. Increasing Quadruples Hitting a Target

You are given one list of n numbers and a target. Count the index quadruples i < j < k < l for which a[i] + a[j] + a[k] + a[l] equals the target. Print the count.

The indices must be strictly increasing, so each position is used at most once and the four positions are distinct. Equal values at different positions still count as different quadruples.

## What most people try first

Four nested loops, which is about n^4 / 24. At n = 1000 that is roughly 4 * 10^10 and far too slow.

The second attempt is the dangerous one, and it is the reason this problem exists. Having seen the version with four separate lists, the instinct is to build a table of ALL pair sums up front, then loop over all pair sums again and look up the complement. That is wrong here, and it is wrong in a way that still produces a plausible-looking number.

The table of all pair sums does not know where its pairs sit. So when you look up the complement of the pair (k, l), the table happily hands back pairs that overlap it, or that sit entirely to its right. You end up counting quadruples that reuse an index, and quadruples in the wrong order, several times over. Nothing crashes. The count is simply too big.

## Keep a barrier and move it as you go

Fix the THIRD index k, and scan k from left to right. Maintain a table holding every pair (i, j) with i < j < k, that is, every pair that lies strictly to the left of k. Then for each l from k + 1 to n - 1, the quadruples ending in (k, l) are exactly the pairs in the table whose sum is target minus a[k] minus a[l], so add that count.

Once k has been fully processed, admit the pairs that END at k, meaning every (i, k) with i < k. Those become available for the next value of k and were correctly unavailable for this one.

## Why this counts each quadruple exactly once

Take any quadruple i < j < k < l that sums to the target. It is counted when the scan reaches that particular k, because by then (i, j) has been admitted (since j < k) and l is in the forward range (since l > k). It is counted at no other k, because k is determined by the quadruple. And nothing invalid is ever counted, because the table only ever holds pairs that finish strictly before k, and l is always strictly after k, so all four indices are distinct and in order.

## The boundary that breaks a careless implementation

The order of the two steps inside the loop over k. The lookups must happen BEFORE the pairs ending at k are admitted. Swap them and the pair (i, k) becomes available for a quadruple whose third index is k, which means index k gets used twice, and the count comes out too high. This is a one-line mistake with no symptom other than a wrong number.

The other is n below 4, where no quadruple exists at all and the answer is 0. The loops must simply produce nothing rather than reading out of range.

## Overflow

The count reaches 500 choose 4, which is 2573031125, past the 32-bit signed limit of 2147483647, so the count needs 64 bits. Values reach 10^9 in magnitude, so the four-way sum reaches 4 * 10^9 and the sums need 64 bits too.

## Cost

The scan over k does O(n) lookups and O(n) insertions per step, so O(n^2) overall, a million steps at n = 1000.

## Worked example

``` a = 1 2 3 4 5 6 target 10 (indices 0 to 5)

k = 0 table empty, nothing to find. admit pairs ending at 0: none k = 1 table empty. admit (0,1) sum 3 k = 2 l = 3..5 need 10 - 3 - a[l] l=3 need 3 table has sum 3 once +1 (0,1,2,3) l=4 need 2 absent l=5 need 1 absent admit (0,2) sum 4, (1,2) sum 5 k = 3 l = 4..5 need 10 - 4 - a[l] l=4 need 1 absent l=5 need 0 absent admit (0,3) sum 5, (1,3) sum 6, (2,3) sum 7 k = 4 l = 5 need 10 - 5 - 6 = -1 absent admit pairs ending at 4 k = 5 no l to the right

answer 1 ```

### Constraints - 1 <= n <= 1000 - each number is between -10^9 and 10^9 - the target is between -4 * 10^9 and 4 * 10^9 - The count reaches 500 choose 4, which is 2573031125, so the count needs a 64-bit type as well as the sums.