Модуль: meet in the middle


Задача

1 /5


Максимальная по модулю подпоследовательность

Теория Нажмите, чтобы прочитать/скрыть

Meet-in-the-middle - способ оптимизации решений, заключающийся в том, чтобы разбить исходную задачу на две половины, решить каждую независимо и затем получить решение исходной задачи путем объединения решений половин.

Соответственно, имеет смысл применять meet-in-the-middle, если выполняются два условия:
1) Время, необходимое для решения половины задачи, асимптотически меньше времени решения целой задачи.
2) По решению задач-половин можно получить решений исходной целой задачи и при этом асимптотически быстрее, чем просто решить целую задачу.

Рассмотрим пример:
Пусть имеется четыре массива целых чисел A, B, C и D. Необходимо выбрать из каждого массива ровно одно число, чтобы сумма этих чисел была равна нулю.
Можно использовать наивное решение, а именно, просто перебрать все возможные варианты. Это будет работать за О(n4).

Однако, мы можем воспользоваться meet-in-the-middle.
Заметим, что a + b + c + d = 0 эквивалентно тому, что (a + b) = -(c + d).
Разделим задачу на две половины, а именно, в первой половине будем использовать только массивы A и B, а во второй половине только C и D.
Переберем все возможные варианты a+b в первой половине и сохраним все значения в хэш-таблицу (unordered_map, HashMap или т.п.). Это работает за O(n2).
Теперь будем перебирать все возможные варианты c+d во второй половине. При рассмотрении определенного варианта будем проверять, есть ли в хэш-таблице значение, ассоциированное с противоположной по знаку текущей суммой (тогда нашли два обратных числа, которые в сумме дают ноль). Эта часть также работает за O(n2).
Здесь у нас нет отдельной фазы "объединения ответов" в один, мы делали это по ходу решения для каждой из половин. В большинстве задач будет аналогичная ситуация.
В итоге мы получили решение за O(n2), используя meet-in-the-middle.

Стоит обратить внимание, что чаще всего meet-in-the-middle применяется при оптимизации экспоненциальных решений, что очень значительно влияет на время работы.

Задача

Дан массив A, состоящий из n целых положительных чисел, и число m.
Выберите последовательность позиций B1, B2, ..., Bk (1 <= B1 < B2 < ... < Bk <= n) такую, чтобы значение  \((\sum_{i=1}^{k} A_{B_i}) mod \; m\) было максимально (то есть, чтобы остаток от деления суммы элементов подпоследовательности на число m был максимально возможным).
Выбранная последовательность можеть быть пустой.

Подсчитайте максимальное возможно значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\).

Входные данные:
В первой строке даны два целых числа n и m (1 <= n <= 35, 1 <= m <= 109)
Во второй строке дано n целых чисел A1, A2, ..., An (1 <= Ai <= 109)

Выходные данные:
Выведите одно число - максимальное значение \((\sum_{i=1}^{k} A_{B_i}) mod \; m\)

Примеры:
 
Входные данные Выходные данные
4 4
5 2 4 1
3
3 20
199 41 299
19

Пояснения:
В первом примере можно выбрать B = {1, 2}. (A1 + A2) mod m = (5 + 2) % 4 = 3.
Во втором примере можно выбрать B = {3}.