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