2378. Three Equal Shares

You are given n numbers. Hand every one of them to exactly one of three people, so that all three end up holding the same total. Count the ways to do it and print the count.

The three people are DISTINGUISHABLE, so handing 1 to the first person and 2 to the second is a different way from handing 2 to the first and 1 to the second. A person may be given nothing, in which case their total is 0 and the other two must also total 0.

## What most people try first

Try every assignment. There are 3^n of them, and at n = 24 that is about 2.8 * 10^11. Far too slow.

The reflex after that is a table indexed by two of the three running totals, since the third is determined by the first two. That is the right instinct and it still does not fit: the numbers reach 10^9, so each total reaches 2.4 * 10^10, and a table indexed by a pair of them is the square of something already too large to allocate.

## Why this is not the subset version

Every earlier problem in this topic splits a two-way choice: an item is taken or it is not. A half of n items therefore has 2^(n/2) outcomes and each one is summarised by a single number, its total, so the join is a lookup or a search on one key.

Here each item goes to one of THREE places. A half has 3^(n/2) outcomes, and one number no longer summarises an outcome, because knowing the total that went to the first group tells you nothing about how the rest was divided between the second and third. So the join key has to carry more than a sum, and working out what the key must be is the whole problem.

The arithmetic still works in your favour, which is the point. 3^24 is about 2.8 * 10^11 and 3^12 is 531441.

## What the key must be

Let the three totals be a, b and c. The condition is a = b = c, which is two equations, not one: a - b = 0 and b - c = 0.

Now notice that both differences are ADDITIVE across a split of the items. If the left half contributes (a1, b1, c1) and the right half contributes (a2, b2, c2), then the whole assignment has a - b = (a1 - b1) + (a2 - b2), and likewise for b - c. So an assignment of the whole list satisfies both equations exactly when the left half's PAIR of differences is the exact negation of the right half's pair.

So enumerate each half into pairs (a - b, b - c), build a map from that pair to how many left assignments produce it, and for each right pair add the count stored at its negation.

## Why differences and not the totals themselves

Storing the three totals would work and would be wasteful: the condition does not care how large the totals are, only that they agree, and the differences capture exactly that while collapsing every assignment that differs only by an overall shift. More importantly the differences are what ADD across the split. The totals add too, but the condition on them is not separable into a left part and a right part, whereas the condition on the differences is. That separability is the whole mechanism.

## The boundary that breaks a careless implementation

Counting the people as interchangeable. If you divide the answer by six to account for permuting three people, you are answering a different question, and the statement pins the people as distinguishable to remove the ambiguity. On three ones the answer is 6, which is exactly the six ways to give one number to each person; a solution that treats the people as a set reports 1.

The second is the all-zero case. If every number is 0 then every one of the 3^n assignments qualifies, which is how the count grows large enough to overflow a 32-bit counter, and a solution that special-cases an empty group wrongly will trip here.

## Overflow

The count reaches 3^24, about 2.8 * 10^11, so it needs 64 bits. The differences reach 2.4 * 10^10 in magnitude and can be NEGATIVE, so the key must be a signed 64-bit pair, and in JavaScript a plain Number is exact only because both are below 2^53.

## Cost

3^(n/2) to build the map and 3^(n/2) lookups. About a million steps at n = 24, against 2.8 * 10^11.

## Worked example

``` numbers 1 1 1 people A, B, C

left half 1 assignments as (a - b, b - c) to A: (1, 0) to B: (-1, 1) to C: (0, -1) map: {(1,0):1, (-1,1):1, (0,-1):1}

right half 1 1 assignments as (a - b, b - c) AA (2,0) AB (0,1) AC (1,-1) BA (0,1) BB (-2,2) BC (-1,0) CA (1,-1) CB (-1,0) CC (0,-2)

for each right pair, look up its negation (0,1) -> need (0,-1) count 1 and (0,1) occurs twice adds 2 (1,-1) -> need (-1,1) count 1 and (1,-1) occurs twice adds 2 (-1,0) -> need (1,0) count 1 and (-1,0) occurs twice adds 2 the rest have no partner

answer 6 ```

### Constraints - 1 <= n <= 24 - 0 <= each number <= 10^9 - The count reaches 3^24, about 2.8 * 10^11, so it needs a 64-bit type. The differences used as a key reach 2.4 * 10^10 in magnitude and can be negative.