ChiefShoe's blog

Question about Consensual Human Cannibalism
By ChiefShoe, history, 5 years ago, In English

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?

  • Vote: I like it
  • +11
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +186 Vote: I do not like it

Top 10 misleading titles.

→ Reply
»
5 years ago, # |
  Vote: I like it +19 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +19 Vote: I do not like it

Seems like it’s dp on humans

→ Reply
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 b Hash 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.

→ Reply