Meet in the Middle
В секцията ще разгледаме техниката "meet-in-the-middle", която е разновидност на "разделяй и владей". За разлика от стандартните алгоритми, базирани на "разделяй и владей", meet-in-the-middle не може да се приложи рекурсивно, но пък обикновено се съчетава с някоя фенси структура данни или трябва някакво интересно наблюдение за да се стигне до достатъчно ефективно решение. В следствие на това повечето задачи, които се решават с meet-in-the-middle са доста "красиви" - балансират мисленето с коденето (имат както хитра идея, така и нетривиална (но не и ужасно сложна) имплементация).Интересно приложение в реалния свят на тази техника е като криптографска атака срещу криптирания, разчитащи на последователност от операции, приложени една след друга.
Единствената тема, която трябва да разгледате за да се справите с тази секция, е Срещане в средата.
Всички задачи в темата ползват под един или друг вид meet-in-the-middle подхода, като ползват различни структури данни за "комбиниране" на двете части.
Prime Pals
8
|
4
Gaming
1
|
8
Lights Out
4
|
50
KHX Tournament
11
|
12
Bulls
14
|
48
Lowest Hash
10
|
43
Alpha
5
|
12
PalMul
4
|
13