MITM: различия между версиями

Текущая версия на 21:27, 8 мая 2020

Идея

Пусть мы умеем полным перебором находить ответ, допустим за $O(2^n * poly(n))$, где $poly(n)$ - полином от $n$, давайте теперь научимся решать эту задачу за $O(2^{n / 2} * poly(n))$

Решение

Давайте разделим задачу на две части - и сначала решим честно перебором за $O(2^{n / 2} * poly(n))$, теперь сделаем следующее : запомним ответы для всех вариантов в какое-то удобное для нас хранилище(в общем случае нам подойдет hash-map), теперь насчитаем ответы для всех вариантов в левой части и для каждого из них посмотрим есть ли подходящий нам пример в правой части.

Автор конспекта: Глеб Лобанов

По всем вопросам пишите в telegram @glebodin

@@ Строка 1: / Строка 1: @@
-==Ограничения==
+==Идея==
+Пусть мы умеем полным перебором находить ответ, допустим за $O(2^n * poly(n))$, где $poly(n)$ - полином от $n$, давайте теперь научимся решать эту задачу за $O(2^{n / 2} * poly(n))$
-Иногда в таких задачах есть подгруппа/или вся задача с маленьким $k$, например $k \leq 10^14$, решим задачу количество чисел < $k$ с суммой цифр - $s$
+==Решение==
-==Альтернативное решение без ДП по цифрам==
+Давайте разделим задачу на две части - и сначала решим честно перебором за $O(2^{n / 2} * poly(n))$, теперь сделаем следующее : запомним ответы для всех вариантов в какое-то удобное для нас хранилище(в общем случае нам подойдет hash-map), теперь насчитаем ответы для всех вариантов в левой части и для каждого из них посмотрим есть ли подходящий нам пример в правой части.
-Давайте разделим число на левую часть(большие 7 разрядов) и правую(меньшие 7 разрядов). Давайте для всех чисел правой части предподсчитаем, сколько из них имеют сумму $x$ и запишем это в массив подсчет, затем будем перебирать левую часть, пусть и числа из левой части сумма - $x$, тогда нам нужно найти количество правых частей с суммой $S - x$(это просто обращение к массиву подсчета), тогда мы научились решать задачу за $\sqrt(k)$
+* [[MITM в задаче о рюкзаке]]
+* [[MITM в задачах на числа]]
+* [[MITM в задаче о числах из 1 и 2, делящихся на M]]
 {{Автор|Глеб Лобанов|glebodin}}
+[[Категория:Конспект]]