Срещане в средата

Meet in the Middle

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

Автор: Александър Георгиев

Разделяй и Владей, ама не съвсем

В темата разделяй и владей разгледахме една мощна техника, чрез която можем да решим ефективно проблеми, отговарящи на следните изисквания:

Проблемът да може да бъде разделен на по-малки, независими под-проблеми;
Под-проблемите да са със същата структура, като оригиналния проблем;
Да има начин, по който да можем ефективно да комбинираме решенията на под-проблемите.

От горните изисквания следва, че ако разделим един проблем на няколко нови, то трябва всяко решение на произволен под-проблем да може да бъде комбинирано с всяко решение на останалите. Така под-проблемите ставаха независими, като не ни интересува кое точно решение намираме за всеки от тях, а просто да намерим някакво решение.

В случаите, в които това не е изпълнено (тоест някое решение на под-проблем може да бъде комбинирано само с някои (потенциално нито едно) решение на другите под-проблеми, не можем да приложим разделяй и владей.

Срещане в средата

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

За целта трябва да са изпълнени следните условия:

Оригиналната задача няма ефективно решение, но може да бъде разделена на две по-малки под-задачи, за които пълното изчерпване все пак е достатъчно бързо;
Има бърз начин, по който можем да намерим дали решение на едната под-задача може да бъде комбинирано с решение на другата.

Тъй като разделяме оригиналния проблем на два под-проблема, обикновено гледаме техният размер да е що-годе сходен - тоест под-задачите са около два пъти по-малки от оригиналната.

Примерна задача

Нека разгледаме следната примерна задача:

Имате 1 ≤ N ≤ 40 на брой числа, за които е изпълнено 1 ≤ A₁, A₂, ..., A_N ≤ 10¹⁶. Искате да проверите дали има тяхно подмножество, чиято сума е равна на някакво число 1 ≤ X ≤ 10¹⁸.

Както можем да видим, броят числа N не е твърде голям, но все пак е достатъчно голям пробването на всички под-множества да не работи, тъй като е със сложност O(2^N), а за N = 40 това би било около 1,000,000,000,000 операции. Това, макар и не много голямо число, би изискало около три часа на модерен компютър. Решение, базирано на идеята от Задачата за Раницата също би било вярно, но пък няма да работи, тъй като ограниченията за X са твърде големи. Какво, тогава можем да направим?

!	Внимавайте за частния случай, в който ви дадат вход с `N` = 1. Тогава едната група ще е празна, и е възможно имплементацията ви да не работи правилно, ако не сте се погрижили специфично за това.

Запознайте се с техниката срещане в средата (пънът ми на английски е по-забавен: "meet meet-in-the-middle"). Окей, 2⁴⁰ е твърде голямо число, но 2²⁰ не е. Ако разделим N-те числа на две (що-годе) равни групи, всяка с около N/2 елемента, и след това намерим всички подмножества във всяка от двете групи, можем ли да комбинираме резултатите от едната група с тези от другата?

Оказва се, че да. Нека намерим всички 2^N/2 суми на подмножества от "лявата" група и ги пъхнем в хештаблица. След това, за всяко от 2^N-N/2-те подмножества R₀, R₁, ... от "дясната" група, можем за O(1) да проверим, дали има сума L = X - R[i] в лявата група (в хештаблицата). В случай, че има, то L + R[i] = X - тоест сме намерили отговор на задачата. В случай, че няма, то можем да твърдим, че цялостно няма подмножество със сума X.

Тук се нуждаем от:

O(2^N/2∙N) операции за да намерим всички подмножества от лявата група и да ги сложим в хештаблица;
O(2^N/2∙N) операции за да намерим всички подмножества от дясната група и да проверим дали има допълващо до X в лявата.

Сумарната сложност на това решение е O(2^N/2∙N), което за N = 40 ще изисква едва около 40 милиона операции - което ще върви за части от секундата на модерен процесор.

Примерна имплементация на горната задача:

bool
 mitm(vector
 <
long
 long
>
 nums,
 long
 long x) {
    unordered_set <
long
 long
>
 sums;
    int
 half =
 (int
)nums.size() /
 2
;
    for
 (int
 mask =
 0
;
 mask <
 (1
 <
<
 half);
 mask+
+) {
        long
 long
 cur =
 0
;
        for
 (int
 i =
 0
;
 i <
 half;
 i+
+)
            if
 (mask &
 (1
 <
<
 i)) cur +
=
 nums[i];
        sums.insert(cur);
    }
    int
 rest =
 (int
)nums.size() -
 half;
    for
 (int
 mask =
 0
;
 mask <
 (1
 <
<
 rest);
 mask+
+) {
        long
 long
 cur =
 0
;
        for
 (int
 i =
 0
;
 i <
 rest;
 i+
+)
            if
 (mask &
 (1
 <
<
 i)) cur +
=
 nums[half +
 i];
        if
 (sums.find(x -
 cur) !
= sums.end())
            return
 true
;
    }
    return
 false
;
}

Комбинация с друг алгоритъм

Забележете, че вместо хештаблица, можеше просто да сортираме всички намерени суми от лявата страна, и след това да ползваме двоично търсене да проверяваме, дали има допълваща сума. Така решението би станало O(2^N/2∙N + 2^N/2∙log(2^N/2)), което все още е O(2^N/2∙N).

Повечето задачи, базирани на meet-in-the-middle използват именно някакъв друг (обикновено относително прост) алгоритъм или структура данни за "комбиниране" на лявата и дясната част. Трикът е да се измисли точно как да се комбинират резултатите в двете половини.

Примерни задачи

Сега ще покажем още няколко задачи, в които можем да приложим meet-in-the-middle.

Братска Подялба с нецели числа

Горе разгледахме задачата за раницата, в която, обаче, числата бяха твърде големи за да приложим стандартното решение. Друга подобна задача е тази за братската подялба, с изискването подялбата да е абсолютно честна (и двете можете да разгледате в темата за динамично оптимиране):

Дадени са ви 40 числа с плаваща запетая. Намерете дали има начин те да бъдат разделени в две под-множества, така че сумата на елементите в едното, да е равна на тази в другото.

Както задачата, така и решението са почти същите, като примерната задача, която разгледахме по-горе. Тук не можем да приложим решение, базирано на динамично оптимиране, тъй като числата са с плаваща запетая (и няма как да ги включим в стейта).
Отново ще се възползваме от малкия брой числа и ще разделим на две под-задачи с по 20 елемента. За всяка под-задача ще намерим всички под-множества, като за всяко от тях ще сметнем разликата между числата, които влизат в под-множеството и тези, които не влизат.

Нека, да кажем, сме намерили някакво такова под-множество в лявата под-задача, където сме взели елементи със сума 42, а оставащите елементи са със сума 13. Така трябва в дясната под-задача да намерим такова под-множество, чиято разлика между взети и невзети елементи е -29.

Ефективното търсене отново можем да реализираме с хештаблица или двоично търсене.

Най-голям XOR

Досега разгледаните задачи бяха относително лесни примери за meet-in-the-middle, тъй като комбинирането на решенията от лявата и дясната под-задачи беше относително тривиално. Това, за съжаление не винаги е така. Нека разгледаме следната задача:

Дадени са ви 1 ≤ N ≤ 42 числа, 1 ≤ A_i ≤ 10¹⁸. Намерете такова тяхно под-множество (съдържащо потенциално всички числа), така че XOR-ът на избраните числа да е максимален.

Броят числа отново ни навежда на мисълта, че ще разделим под-задачата на две с по (максимум) 21 елемента. 2²¹ е достатъчно малко за да върви доста бързо.

Как, обаче, можем да комбинираме събсет (реално число, след като XOR-нем числата в него) от лявата под-задача с такъв от дясната? Имаме ли някакъв начин ефективно да намираме оптималното число, с което XOR-ът би бил максимален?

Оказва се, че да (всъщност това е известен трик, покрит в последната секция на USACO Training-a). Ще ползваме структурата данни префиксно дърво (Trie), което в случая ще е двоично и ще направим по битовете на резултатните числа от едната под-задача. Всеки резултат (XOR на събсет от числа от едната под-задача) ще разгледаме в неговия двоичен запис и ще вкараме в Trie, бит по бит. Така, когато искаме да попитаме каква е оптималната комбинация за дадено число X, ще тръгнем по trie-а, и, започвайки от най-старшия бит на X:

Ако текущата двоична цифра на X е 0, ще проверим дали има продължение с 1 от текущия връх в Trie-а (ако има, то XOR-ът ще е 1, което е добре за нас)
Ако текущата двоична цифра на X е 1, ще проверим дали има продължение с 0 от текущия връх в Trie-а (ако има, то XOR-ът ще е отново 1, което е добре за нас)

В случай, че няма дадено продължение, което ще е "добре за нас", то продължаваме с другото (такова със сигурност ще има). Вярно, двоичната цифра на текущата позиция в XOR-а ще е нула, но пък няма какво друго да направим - вече сме взели оптимални по-старши цифри, които допринасят повече за отговора.

Четворка с нулева сума

Тук пък ще разгледаме една популярна задача от интервюта, чието оптимално решение е полиномиално, но пък ограниченията са достатъчно големи за да не върви достатъчно бързо (без да приложим срещане в средата):

Даден ви е масив с 1 ≤ N ≤ 1000 елемента. Всеки от елементите е в границите -10¹⁶ ≤ A_i ≤ 10¹⁶. Проверете дали има четворка с нулева сума.

Тази задача е малко по-сложна версия на тройка с нулева сума. Ако просто напишем най-тривиалната идея (с четири вложени for() цикъла), ще постигнем сложност O(N⁴), което е много над исканото. Ако сортираме числата и търсим последното с двоично търсене, ще получим O(N³∙logN). Дори ако ползваме най-доброто решение, което показахме във версията с три числа с нулева сума, все пак ще сме със сложност O(N³).

Забележете, че тук трябва да ползваме хешмап, вместо хешсет, тъй като трябва да намерим двойка, която е непресичаща се с първата такава - тоест трябва да можем да кажем кои две числа са участвали в двойката. В противен случай рискувате да отговорите, че има четворка с нулева сума от масив с три числа (например за {-10, 2, 4} можете да дадете (-10 + 4) + (2 + 4) == 0).

Можем, обаче, да съчетаем meet-in-the-middle с едно от показаните решения, и тогава нещата ще се получат. Първо ще намерим всички двойки и ще ги набутаме в един хешмап за O(N²). След това ще обходим пак всички двойки и ще търсим дали има друга двойка, която да дава същото число, като сумата на текущата двойка, но с обратен знак, за още O(N²). Тъй като двете обхождания са независими, цялата сложност на това решение е O(N²).

Обръщане на низове

Друг пример за задача с полиномиално решение, чиито ограничения просто са твърде големи:

Дадени са ви два стринга с дължина 1 ≤ N ≤ 50. Имате право да правите следната операция: избирате подстринг на първия низ и го обръщате наобратно. Възможно ли е с най-много 4 такива операции да получите от първия стринг - втория?

Наивното решение би било със сложност O(N⁹) - за всяка операция пробваме всяка двойка индекси, като накрая проверяваме дали получения стринг е еднакъв с търсения.
Това, разбира се, за тези ограничения е твърде много - би се нуждало от около две седмици за да завърши. Все пак, две седмици не е някакво чудовищно дълго време.

Наблюдението, което трябва да направим, е, че операцията "обръщане на подстринг" е симетрична. Вместо да я приложим 4 пъти в първия стринг, можем да я приложим два пъти в първия и два пъти във втория - ако получим поне един еднакъв резултат прилагайки я в първия и във втория стринг, то реално сме можели да ползваме същите индекси само в първия за да получим (непроменен) втория.

Така реално се нуждаем от O(N⁵) за да намерим всички възможни резултатни стрингове, прилагайки до 2 пъти операцията в първия стринг, и още O(N⁵), за да намерим всички възможни резултатни стрингове, прилагайки я до 2 пъти във втория. Самите резултати можем да пазим в hashset, като така имаме O(1) проверка дали има даден резултатен стринг в другата група. Цялото решение става O(N⁵), което е достатъчно бързо (ще върви за около секунда).

Още задачи

А ето и няколко други задачи, в които можете да упражните meet-in-the-middle.

Задачата Gaming е по-скоро графова, но след като се сметне цената на всяко ниво, остава да се разпределят нивата между двамата играчи ползвайки meet-in-the-middle.

Задачата KHXTournament беше първоначално подготвена за Балканската Олимпиада по Информатика, 2015 г., която се проведе в България, но в крайна сметка остана резервна и по-късно дадох на зимните 2016. Тя беше относително лесна, тъй като не е много сложно да се види как точно да приложим срещане в средата.

Задачата Bulls дадох в TopCoder и изискваше по-нестандартно разделяне на под-проблеми. След като знаете, че става с meet-in-the-middle, обаче, би трябвало да нямате голям проблем да се справите с нея.

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

Референции

Страницата е посетена 5295 пъти.

Предложете корекция

Selected text (if you see this, there is something wrong)

(Незадължително) E-mail за обратна връзка: