Meet in the Middle

Встреча посередине

e-olymp 11431

IOI Prep Camp — День 1 | Аббас Алиев
28 апреля 2026

Условие задачи

e-olymp 11431 — Встреча посередине

Дан массив из n целых чисел.
Сколькими способами можно выбрать подмножество элементов с суммой ровно s?

Ограничения:
n ≤ 40 • s ≤ 10⁹ • t_i ≤ 10⁹

Пример

Массив: [3, 1, 4, 2], s = 5
Ответ: 2 (подмножества {3, 2} и {1, 4})

Первая мысль: перебрать все подмножества

Каждый элемент: взять или не взять — 2 варианта

n элементов → 2ⁿ подмножеств

n = 40 → 2⁴⁰ подмножеств. Сколько это?

2⁴⁰ = 1 099 511 627 776

≈ 10¹² — триллион

При 10⁸ операций/сек → ~10 000 секунд

10 000 секунд = 2 часа 47 минут ⏰

Лимит времени: 1 секунда ❗

TLE

А что если n было бы 20?

	n = 40	n = 20
Подмножеств	2⁴⁰ ≈ 10¹²	2²⁰ ≈ 10⁶
Время	~10 000 сек	< 0.01 сек
Вердикт	TLE	OK

10⁶ — это мгновенно! Как это использовать?

Идея: разрежь массив пополам

a₁

a₂

...

a₂₀

a₂₁

a₂₂

...

a₄₀

✂

a₁

a₂

...

a₂₀

Левая: 20 элементов

2²⁰ ≈ 10⁶ — БЫСТРО!

a₂₁

a₂₂

...

a₄₀

Правая: 20 элементов

2²⁰ ≈ 10⁶ — БЫСТРО!

Любое подмножество = левая часть + правая часть

S = S_L ∪ S_R

sum(S) = sum(S_L) + sum(S_R)

Пример: [3, 1, 4 | 2, 5, 7], s = 10

Подмножество {3, 7}:	S_L = {3}, S_R = {7}	sum = 3 + 7 = 10 ✔
Подмножество {1, 4, 5}:	S_L = {1, 4}, S_R = {5}	sum = 5 + 5 = 10 ✔

💡 Ключевая идея

Нам нужно: sum(S_L) + sum(S_R) = s
То есть: sum(S_R) = s − sum(S_L)

Почему это работает математически? Любое подмножество всего массива можно разделить на две части: что мы взяли из левой половины и что мы взяли из правой. И сумма всего подмножества — это просто сумма левой части плюс сумма правой. Вот пример: массив [3, 1, 4, 2, 5, 7], нужна сумма 10. Подмножество {3, 7} — это S_L = {3} с суммой 3 и S_R = {7} с суммой 7, итого 10. Нам нужно: сумма левой части плюс сумма правой = s. То есть если мы знаем сумму левой части, то мы точно знаем, какая сумма нужна от правой.

Алгоритм Meet in the Middle: 3 шага

Шаг 1: Генерация — Перебрать все 2^n/2 подмножеств левой половины, записать их суммы в массив A

Шаг 2: Генерация + Сортировка — Перебрать все 2^n/2 подмножеств правой половины, записать их суммы в массив B. Отсортировать B.

Шаг 3: Комбинирование — Для каждого a из A бинарным поиском найти, сколько элементов B равны (s − a). Суммировать.

Итоговая сложность

Полный перебор: 2⁴⁰ ≈ 10¹²

↓

Левая: 2²⁰ ≈ 10⁶

Правая: 2²⁰ ≈ 10⁶

↓

Комбинирование: 10⁶ · log(10⁶) ≈ 2·10⁷

Итого: ~2·10⁷ вместо 10¹²

Аналогия: две колоды карт

Колода A:
суммы левой половины

↔

Колода B:
суммы правой половины
(отсортированы!)

❌ Наивный: сравнить каждую с каждой → m² пар

✔ Умный: отсортировать правую → m · log(m)

💡 Ключевая идея

Meet-in-the-middle — это та же идея, только «колоды» — это множества всех подмножеств каждой половины

Давайте проведу аналогию. Представьте, что у вас две колоды карт. На каждой карте написано число. Вам нужно найти пару — одну из первой колоды и одну из второй — с суммой s. Наивный способ: сравнить каждую карту с каждой — это m в квадрате операций. Но если мы отсортируем вторую колоду, то для каждой карты из первой мы можем бинарным поиском найти нужную пару — и это m на логарифм m. Meet in the Middle — это ровно та же идея. Только наши «колоды» — это не отдельные числа, а суммы всех подмножеств каждой половины массива.

Перебор подмножеств через битовые маски

Подмножество из n элементов ↔ двоичное число из n бит

Бит i = 1 → элемент i включён | Бит i = 0 → не включён

Маска (10)	Маска (2)	Подмножество	Сумма
0	`000`	{}	0
1	`001`	{a}	a
2	`010`	{b}	b
3	`011`	{a, b}	a + b
4	`100`	{c}	c
5	`101`	{a, c}	a + c
6	`110`	{b, c}	b + c
7	`111`	{a, b, c}	a + b + c

2³ = 8 масок = 8 подмножеств — ни одно не пропущено и нет повторов

Теперь разберёмся, как конкретно перебрать все подмножества. Используем битовые маски. Идея: каждое подмножество из n элементов можно закодировать двоичным числом из n бит. Если i-й бит равен 1 — элемент включён в подмножество, если 0 — не включён. Вот таблица для трёх элементов: маска 000 — пустое множество, маска 001 — только первый элемент, маска 011 — первый и второй, маска 111 — все три. Всего 2^3 = 8 масок, ровно 8 подмножеств — каждое ровно один раз.

Нужные битовые операции

1. 1 << i — число с единственной единицей в позиции i
1 << 0 = 1 = 1 1 << 1 = 10 = 2 1 << 2 = 100 = 4

2. mask | (1 << i) — установить бит i
011 | 100 = 111 (добавили элемент 2)

3. mask & (1 << i) — проверить, установлен ли бит i
101 & 010 = 000 (бит 1 не установлен)

4. 1 << n — это 2ⁿ (количество всех масок)
1 << 3 = 1000 = 8

Генерация сумм: наивный способ


// Наивная версия — понятная, но медленнее
vector<long long> sums;
int n = arr.size();
for (int mask = 0; mask < (1 << n); mask++) {
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        if (mask & (1 << i))  // бит i установлен?
            sum += arr[i];
    }
    sums.push_back(sum);
}

if (mask & (1 << i)) — «Проверяем каждый бит маски»

Сложность: O(2ⁿ · n) — для каждой маски перебираем все n бит

Это работает, но можно быстрее!

Умная генерация: используем уже вычисленные суммы

💡 Ключевая идея

Сумма подмножества с маской mask | (1 << i) = сумма подмножества с маской mask + arr[i]

«подмножество с элементом i» = «подмножество без элемента i» + arr[i]


void genSums(vector<long long>& arr, vector<long long>& sums) {
    int n = arr.size();
    sums.resize(1 << n);
    sums[0] = 0;  // пустое подмножество
    for (int i = 0; i < n; i++)
        for (int mask = 0; mask < (1 << i); mask++)
            sums[mask | (1 << i)] = sums[mask] + arr[i];
}

Ключевая строка: sums[mask | (1 << i)] = sums[mask] + arr[i]

Пример: genSums для массива [3, 1, 4]

arr = [3, 1, 4] (индексы 0, 1, 2)

Начало: sums[000] = 0 (пустое множество)

i = 0 (arr[0] = 3): mask = 0 → sums[001] = sums[000] + 3 = 3 {} → {3}

i = 1 (arr[1] = 1):
mask=0: sums[010] = sums[000] + 1 = 1 {} → {1}
mask=1: sums[011] = sums[001] + 1 = 3+1 = 4 {3} → {3,1}

i = 2 (arr[2] = 4):
mask=0: sums[100] = sums[000] + 4 = 4 {} → {4}
mask=1: sums[101] = sums[001] + 4 = 3+4 = 7 {3} → {3,4}
mask=2: sums[110] = sums[010] + 4 = 1+4 = 5 {1} → {1,4}
mask=3: sums[111] = sums[011] + 4 = 4+4 = 8 {3,1} → {3,1,4}

Инд.	Маска	Подмн.	Сумма
0	000	{}	0
1	001	{3}	3
2	010	{1}	1
3	011	{3,1}	4
4	100	{4}	4
5	101	{3,4}	7
6	110	{1,4}	5
7	111	{3,1,4}	8

Давайте проследим genSums на конкретном примере. Массив [3, 1, 4], три элемента. Начинаем: sums[000] = 0, пустое множество. Шаг i = 0, элемент 3. Маска перебирает только 0, потому что 1 сдвиг 0 = 1. Берём sums[000] = 0, прибавляем 3, получаем sums[001] = 3. Мы только что создали подмножество {3} из пустого. Шаг i = 1, элемент 1. Маска перебирает 0 и 1. Из sums[000] = 0 делаем sums[010] = 1 — это подмножество {1}. Из sums[001] = 3 делаем sums[011] = 4 — это {3, 1}. Видите? Мы берём каждое подмножество, которое мы уже построили, и добавляем в него новый элемент. Шаг i = 2, элемент 4. Теперь масок четыре: 0, 1, 2, 3. Из каждого уже вычисленного подмножества создаём новое, добавляя 4. В конце у нас все 8 подмножеств с правильными суммами.

Почему это работает: «удвоение» на каждом шаге

Каждый новый элемент удваивает число подмножеств:
было k — стало 2k

Полный пример: [3, 1, 4, 2, 5, 7], s = 10

Шаг 0: Разделяем

Шаг 1: Суммы левой половины → массив A

Подмн.	Сумма	Подмн.	Сумма
{}	0	{4}	4
{3}	3	{3,4}	7
{1}	1	{1,4}	5
{3,1}	4	{3,1,4}	8

A = [0, 3, 1, 4, 4, 7, 5, 8]

Шаг 2: Суммы правой половины + сортировка

Подмн.	Сумма	Подмн.	Сумма
{}	0	{7}	7
{2}	2	{2,7}	9
{5}	5	{5,7}	12
{2,5}	7	{2,5,7}	14

B до сортировки: [0, 2, 5, 7, 7, 9, 12, 14]

B после сортировки: [0, 2, 5, 7, 7, 9, 12, 14]

Два элемента 7 рядом — одинаковые суммы от разных подмножеств ({2,5} и {7}) — это нормально!

Шаг 3: Комбинирование — ищем пары

A = [0, 3, 1, 4, 4, 7, 5, 8] B = [0, 2, 5, 7, 7, 9, 12, 14] s = 10, need = 10 − a

a из A	need = 10 − a	Вхождений need в B	Вклад
0	10	0	0
3	7	2	2
1	9	1	1
4	6	0	0
4	6	0	0
7	3	0	0
5	5	1	1
8	2	1	1

ans = 0 + 2 + 1 + 0 + 0 + 0 + 1 + 1 = 5

5 подмножеств с суммой 10

Проверка: 5 подмножеств с суммой 10

#	S_L	S_R	sum(S_L) + sum(S_R)	Подмножество
1	{3}	{2, 5}	3 + 7 = 10	{3, 2, 5}
2	{3}	{7}	3 + 7 = 10	{3, 7}
3	{1}	{2, 7}	1 + 9 = 10	{1, 2, 7}
4	{1, 4}	{5}	5 + 5 = 10	{1, 4, 5}
5	{3, 1, 4}	{2}	8 + 2 = 10	{3, 1, 4, 2}

✔ Все 5 правильные!

Как считать количество: lower_bound и upper_bound

B = [0, 2, 5, 7, 7, 9, 12, 14] Ищем: need = 7


long long need = s - a;
ans += upper_bound(B.begin(), B.end(), need)
     - lower_bound(B.begin(), B.end(), need);

💡 Запомнить

lower_bound(x) → первый элемент ≥ x
upper_bound(x) → первый элемент > x
Разница = количество элементов, равных x

Как именно мы считаем, сколько раз число встречается в отсортированном массиве? Используем стандартные функции C++: lower_bound и upper_bound. lower_bound возвращает итератор на первый элемент, больший или равный x. upper_bound — на первый элемент, строго больший x. Разность — это ровно количество элементов, равных x. Вот пример: ищем 7 в массиве B. lower_bound показывает на позицию 3, upper_bound — на позицию 5. Разность 5 минус 3 = 2. Именно два элемента 7 в массиве. Обе функции работают за O(log n) на отсортированном массиве.

Полное решение (C++)


#include <bits/stdc++.h>
using namespace std;

void genSums(vector<long long>& arr, vector<long long>& sums) {
    int n = arr.size();
    sums.resize(1 << n);
    sums[0] = 0;
    for (int i = 0; i < n; i++)
        for (int mask = 0; mask < (1 << i); mask++)
            sums[mask | (1 << i)] = sums[mask] + arr[i];
}

int main() {
    int n;
    long long s;
    scanf("%d %lld", &n, &s);
    vector<long long> arr(n);
    for (int i = 0; i < n; i++) scanf("%lld", &arr[i]);

    int h = n / 2;
    vector<long long> left(arr.begin(), arr.begin() + h);
    vector<long long> right(arr.begin() + h, arr.end());

    vector<long long> A, B;
    genSums(left, A);
    genSums(right, B);

    sort(B.begin(), B.end());

    long long ans = 0;
    for (long long a : A) {
        long long need = s - a;
        ans += upper_bound(B.begin(), B.end(), need)
             - lower_bound(B.begin(), B.end(), need);
    }
    printf("%lld\n", ans);
}

genSums — генерация sort — сортировка цикл — комбинирование

Разбор: чтение данных и разделение массива


int h = n / 2;
vector<long long> left(arr.begin(), arr.begin() + h);
vector<long long> right(arr.begin() + h, arr.end());

⚠️ Важно

Если n нечётное (например, n = 7): h = 3, left = 3 элемента, right = 4 элемента. Это нормально: 2³ + 2⁴ = 8 + 16 = 24 — всё ещё быстро. Лучше правая половина чуть больше, чем левая (2²¹ > 2¹⁹, но обе быстрые).

Ловушка: типы данных

⚠️ Осторожно: переполнение!

Суммы могут быть до 20 · 10⁹ (20 элементов по 10⁹)

int вмещает до ~2 · 10⁹ — переполнение!

Нужен long long для сумм и для s


long long s;              // не int!
vector<long long> arr(n); // не int!
// В genSums:
vector<long long>& sums;  // не int!

⚠️ Особенно опасно

1 << n при n ≥ 31 → переполнение int!
Решение: 1LL << n или (long long)1 << n

Всегда проверяйте: может ли сумма/произведение переполнить int?

Анализ сложности

Этап	Операций	Пояснение
genSums(left)	2^n/2	Генерация сумм левой половины
genSums(right)	2^n/2	Генерация сумм правой половины
sort(B)	2^n/2 · n/2	Сортировка
Цикл + бин. поиск	2^n/2 · n/2	Для каждого a поиск в B

Итого: O(2^n/2 · n/2)

Для n = 40: 2²⁰ · 20 = 1 048 576 · 20 ≈ 2 · 10⁷

10¹²

Полный перебор

→

2 · 10⁷ ✔

Meet in the Middle

Ускорение: в 50 000 раз

А хватит ли памяти?

Два массива A и B, каждый размером 2^n/2 = 2²⁰ ≈ 10⁶

Каждый элемент — long long = 8 байт

Итого: 2 · 10⁶ · 8 = 16 МБ

Типичный лимит памяти: 256 МБ

✔

OK — с огромным запасом!

Когда применять Meet in the Middle?

💡 Ключевая идея — Паттерн

Полный перебор O(2ⁿ) или O(n!) слишком медленный, но O(2^n/2) или O((n/2)!) — допустимо.
Разбиваем задачу на две половины, решаем отдельно, комбинируем результаты.

Характерные признаки:

n ≈ 30–50 (слишком много для 2ⁿ, достаточно для 2^n/2)
Ответ зависит от двух независимых частей, которые можно скомбинировать
Комбинирование можно сделать быстро (сортировка + бин. поиск, хеш-таблица, два указателя)

n ≤ 20
Полный перебор
2ⁿ ≈ 10⁶

n = 21..40
Meet in the Middle
2^n/2 ≈ 10⁶

n > 40
Другой подход
(DP, жадный...)

Где ещё применяется Meet in the Middle?

1. Сумма подмножеств (наша задача) — n ≤ 40, сумма = s

2. 4SUM — даны 4 массива, найти a+b+c+d = 0. Разбиваем на (a+b) и (c+d)

3. Дискретный логарифм (Baby-step Giant-step) — найти x: a^x ≡ b (mod p). Разбиваем x = i·m + j

4. Задача о рюкзаке при малом n — n ≤ 40, вместо DP по весу

5. Перебор перестановок — n! слишком много, но можно разбить на две группы

Профессор Медведев разберёт эту технику глубже на своих лекциях

Частые ошибки при реализации

1. Переполнение int: Суммы до 20 · 10⁹ → long long. 1 << n при n ≥ 31 → переполнение! Пишите 1LL << n

2. Забыли отсортировать B: Без сортировки lower_bound/upper_bound дают мусор! Отсортировать нужно ОДИН раз, перед циклом.

3. Неправильное разделение: arr.begin() + h — не arr.begin() + h + 1! Конструктор vector(begin, end) берёт полуинтервал [begin, end)

4. int для ответа: Ответ может быть до 2⁴⁰ ≈ 10¹² → long long ans

Перечислю типичные ошибки. Первая и самая частая — переполнение. Суммы нужно хранить в long long. Особенно коварно: оператор сдвига 1 << n. Если n >= 31, то 1 — это int, и 1 << 31 — это переполнение! Пишите 1LL << n. Вторая ошибка: забыли отсортировать B перед бинарным поиском — получаете мусор. Третья: неправильно разрезали массив — помните, что конструктор вектора берёт полуинтервал. Четвёртая: ответ тоже может быть огромным — до 2^40 — поэтому ans тоже long long.

Вариант: unordered_map вместо бинарного поиска


unordered_map<long long, int> cnt;
for (long long b : B)
    cnt[b]++;

long long ans = 0;
for (long long a : A)
    ans += cnt[s - a];

	Сортировка + бин. поиск	unordered_map
Сложность	O(2^n/2 · n/2)	O(2^n/2) в среднем
Константа	Маленькая	Побольше (хеширование)
Надёжность	Всегда работает	Редко — антихеш-тесты
Рекомендация	На олимпиаде — надёжнее	Для быстрого прототипа

Подведём итоги

1. Суть приёма

2⁴⁰ — это слишком, но 2 × 2²⁰ — нормально.
Разделяй и комбинируй.

2. Три шага

• Генерируем суммы подмножеств каждой половины (genSums)
• Сортируем одну половину
• Бинарным поиском считаем пары

3. Когда применять

n ≈ 30–50, задача на перебор, ответ можно собрать из двух частей

e-olymp 11431 — Встреча посередине

Попробуйте сдать!

Вопросы?

https://www.e-olymp.com/ru/problems/11431

Домашнее задание: сдать задачу на e-olymp

Meet in the Middle

Условие задачи

Первая мысль: перебрать все подмножества

n = 40 → 240 подмножеств. Сколько это?

А что если n было бы 20?

Идея: разрежь массив пополам

Любое подмножество = левая часть + правая часть

Алгоритм Meet in the Middle: 3 шага

Итоговая сложность

Аналогия: две колоды карт

Перебор подмножеств через битовые маски

Нужные битовые операции

Генерация сумм: наивный способ

Умная генерация: используем уже вычисленные суммы

Пример: genSums для массива [3, 1, 4]

Почему это работает: «удвоение» на каждом шаге

Полный пример: [3, 1, 4, 2, 5, 7], s = 10

Шаг 2: Суммы правой половины + сортировка

Шаг 3: Комбинирование — ищем пары

Проверка: 5 подмножеств с суммой 10

Как считать количество: lower_bound и upper_bound

Полное решение (C++)

Разбор: чтение данных и разделение массива

Ловушка: типы данных

Анализ сложности

А хватит ли памяти?

Когда применять Meet in the Middle?

Где ещё применяется Meet in the Middle?

Частые ошибки при реализации

Вариант: unordered_map вместо бинарного поиска

Подведём итоги

1. Суть приёма

2. Три шага

3. Когда применять

Вопросы?

n = 40 → 2⁴⁰ подмножеств. Сколько это?