Найти сумму x из элементов из 4 последовательностей

Question

Это моя проблема:

Учитывая число x и 4 последовательности A, B, C и D, каждое из n чисел, решают, существуют ли некоторые числа a из A, b из B, c из C и d из D, такие что x = a+b+c+ д. Разрешены операции сравнения, добавления и замены. Разработайте эффективный алгоритм для решения этой проблемы с наихудшим временем выполнения менее n^4.

Я понятия не имею, с чего начать, и буду признателен за помощь!

Answer 1

Вы можете сделать следующее:

1. создать массивы парных сумм AB=A+B, CD=C+D, суммируя каждую пару между A и B и одинаковую для C и D (AB и CD являются массивами из n^2 элементов каждый) - O (n^2)
2. Сортировать массивы AB, CD - O(n^2 log(n)) (благодарность user58697 за этот подход. Ранее я предлагал другой подход, который, как мне казалось, будет более сложным, но (с) он указал на мою ошибку.)
3. Назначить индексы abi = (n^2-1), cdi = 0

4. Изучите AB[abi]+CD[cdi], проверьте условия и индексы увеличения / уменьшения

   1. Вычислить сумму =AB[abi]+CD[cdi]
   2. Если сумма равна x: такая комбинация существует! (алгоритм остановки)
   3. Если сумма
   4. Если сумма> x: уменьшить значение abi (--abi)
   5. Если (abi < 0) ИЛИ (cdi >= n^2): НЕТ ТАКОЙ КОМБИНАЦИИ! (алгоритм остановки)
   6. Вернитесь к 4.1.

   Каждый раз, когда мы выполняем шаг 4, индекс либо увеличивается, либо уменьшается (или алгоритм останавливается), поэтому мы выполняем шаг 4 максимально 2*n^2 раза (количество элементов в обоих массивах) - O (n^2)

Таким образом, в целом мы имеем O(n^2 log(n))