tgoop.com/sbornik_olprog/175
Last Update:
MITM - Meet In The Middle
Предисловие:
По мотивам задачи C 1-го дня региона...
В основном метод призван помочь, когда вы знаете решение задачи, но оно не проходит по TL, а вот то же решение при ограничениях в 2 раза меньше уже проходит. Обычно в таких задачах асимптотика 2^n и поэтому деление на 2 помогает - получаем 2^{n/2}.
По теории метод простой: делим задачу на две одинаковых (или почти) один раз (не путать с "разделяй и властвуй") и потом объединяем результаты двух половин.
Звучит просто и обычно как поделить на две задачи понятно, но трудности могут возникнуть в объединении. Также, в таких задачах может возникнуть проблема в придумывании решения без деления пополам, так как часто это какое-нибудь ДП по подмножествам.
Поэтому надо нарешать задач на него, чтобы хорошенько прочувствовать
Пререквизиты:
🔙 Перебор всех подмножеств битмасками
🔙 Динамическое программирование по подмножествам
Теория:
📼 Открытая лекция Тинькофф Поколения - разбор набора задач по теме на доске без кода
📼 Видео от красного на кф Errichto - разбор набора задач с кодом, но на английском
Первые задачи:
💻 CSES 1
💻 CSES 2
KIT контест по теме с периодически пополняемыми задачами:
Вопросы на понимание темы:
В этот раз без них, так как надо задачи решать
Автор: https://www.tgoop.com/KogutIvanTutoring
Теги: #алгоритмы #методы #meet_in_the_middle #динамическое_программирование
