Meet in the Middle

В секцията ще разгледаме техниката "meet-in-the-middle", която е разновидност на "разделяй и владей". За разлика от стандартните алгоритми, базирани на "разделяй и владей", meet-in-the-middle не може да се приложи рекурсивно, но пък обикновено се съчетава с някоя фенси структура данни или трябва някакво интересно наблюдение за да се стигне до достатъчно ефективно решение. В следствие на това повечето задачи, които се решават с meet-in-the-middle са доста "красиви" - балансират мисленето с коденето (имат както хитра идея, така и нетривиална (но не и ужасно сложна) имплементация).
Интересно приложение в реалния свят на тази техника е като криптографска атака срещу криптирания, разчитащи на последователност от операции, приложени една след друга.

Единствената тема, която трябва да разгледате за да се справите с тази секция, е Срещане в средата.

Всички задачи в темата ползват под един или друг вид meet-in-the-middle подхода, като ползват различни структури данни за "комбиниране" на двете части.
Мрън!