I am struggling with a question about Consensual Human Cannibalism:

You have n (1 <= n <= 2000) plates of humans, and each plate has a deliciousness assosiated with it: a1, a2, .., a_n, and you must count: How many quadruplets of plates (w,x,y,z) are there such that a_w+a_x+a_y+a_z = 0 (the deliciousnesses sum to 0)

I can only think of a O(n^4) slution.. any ideas?

Top 10 misleading titles.

Can you link the problem? I don't want to google for this one :Dd

Very Similar Question, Without the Suspicious Title

https://www.spoj.com/problems/SUMFOUR/

Seems like it’s dp on humans

If there are 4 zeros, that’s your answer.

Otherwise, put all plates of flesh in a set L, and make an empty set R. Store two sets of all possible pair wise sums in sets L and R. You can maintain this easily as you alter the sets.

The solution idea is as follows: repeatedly move an element from set L to set R. Check if any of the pairs that plate of human flesh was involved in is also a pair on set R. If it is, you have your answer. If not, subtract out all pairs from set L and add all new pairs to the pairs you can make with set R, since the new flesh will be in set R.

This is n^2 worst case since you move an element from L to R n times, and each one takes O(n) time. There’s also an extra log factor if you use treesets instead of hash sets.

Oh heck, this is so much less case-work than what I did. Noice

I got an O(N^2) which involves casing it up into three cases:

a: Sum of one positive, three non-positive b: Sum of two positives, two non-negatives c: Sum of three positives, one non-negative d: All zero cases

Make a list of the positive values in a -> P, and a list of the negative/zero values in a -> NZ.

Case a and c (without loss of generality these are the same case)Make a HashSet for every pair of elements (p + nz) such that p is in P and nz is in NZ. Now you'll want to start removing elements from this HashSet; for each element p in P, remove all entries in the HashSet which use P; then loop through already-removed positive values (getting their sum) and for each of those sums, check if it's in the HashSet. (It might need to be a HashMap, actually, to count the number of occurrences.)Case bHash all sums of pairs of positive values, then loop through all pairs of negative values to check if it's in the HashSet of positive sums (again, it might need to be a HashMap).Case d(The number of zeros there are) choose 4.