Find a sum x from elements from 4 differens sequences

Question

This is My problem:

Given a number x and 4 sequences A, B, C and D, each of n numbers, decide whether there exists some numbers a from A, b from B, c from C and d from D such that x = a+b+c+d. Operations alowed are comparisons, additions and swaps. Design an efficient algorithm to solve this problem with a worst case running time less than n^4.

I have no idea where to start and would appreciate some help!

Answer 1

You could do the following:

1. create pair-sums arrays AB=A+B, CD=C+D by summing every pair between A and B and the same for C and D (AB and CD are arrays of n^2 elements each) - O(n^2)
2. Sort arrays AB, CD - O(n^2 log(n)) (credit to user58697 for this approach. Earlier I had suggested a different approach that I thought would have better complexity, but (s)he pointed out my mistake.)
3. Assign indices abi = (n^2-1), cdi = 0

4. Investigate AB[abi]+CD[cdi], check conditions and increment/decrement indices

   1. Compute sum=AB[abi]+CD[cdi]
   2. If sum equals x: SUCH COMBINATION EXISTS! (stop algorithm)
   3. If sum < x: increment cdi (++cdi)
   4. If sum > x: decrement abi (--abi)
   5. If (abi < 0) OR (cdi >= n^2): NO SUCH COMBINATION EXISTS! (stop algorithm)
   6. Go back to 4.1.

   Every time we do step 4 an index is either incremented or decremented (or the algorithm stops) so we are doing step 4 at most 2*n^2 times (the number of elements across both arrays) - O(n^2)

So all in all we have O(n^2 log(n))