298. Quadruples That Cancel Out
You are given four lists A, B, C and D, each of n integers. Count the
quadruples of INDICES (i, j, k, l) with:
A[i] + B[j] + C[k] + D[l] == 0
Indices are counted, not values, so repeated values produce repeated quadruples
and the count can be as large as n^4.
Four nested loops cost O(n^4) and are hopeless at n = 200. The move is to cut
the problem in half. Build a map from every sum A[i] + B[j] to how many pairs
produce it, which is n^2 work. Then for every pair from C and D, look up how
many first-half pairs equal the negation of its sum.
Total cost O(n^2), and the idea is called meet in the middle. Note what makes
it work: the four lists are independent, so a choice from the first half never
constrains the second.
The counts, not the sums, are what the map must hold. Storing only which sums exist loses every repeat and gives the wrong answer on the very first test with duplicates.
Constraints - `1 ≤ n ≤ 200` - `-100000000 ≤ value ≤ 100000000`
Input
The first line contains an integer n.
The next four lines each contain n space-separated integers: the lists A, B, C and D in that order.
Output
Print one integer: how many index quadruples sum to zero.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.