De ce contează?
Doi prieteni caută o comoară într-un munte cu tuneluri care se bifurcă la
fiecare pas: după 40 de bifurcații există 2^40 de trasee — o viață nu ajunge
să le parcurgi pe toate dintr-un singur capăt. Așa că pornesc din capete opuse:
fiecare explorează doar 40/2 = 20 de bifurcații, adică 2^20 de trasee — cam un
milion, nu un trilion — și își compară notițele la mijloc. Un traseu complet
există exact când o jumătate de-a lui se leagă de o jumătate de-a celuilalt.
Meet in the Middle face exact asta: taie problema în două, enumeră fiecare
jumătate separat și le „întâlnește" la mijloc.
Intuiția
Multe probleme cer să alegi o submulțime din n elemente care îndeplinește o
condiție — de exemplu, o submulțime cu suma exact S. Numărul de submulțimi e
2^n, deci la n = 40 ai peste o mie de miliarde de variante: imposibil de
parcurs. Ideea-cheie e că 2^n se sparge frumos: dacă tai elementele în două
jumătăți de câte n/2, fiecare jumătate are doar 2^(n/2) submulțimi. Generezi
separat sumele celor două jumătăți și le combini inteligent — în loc să le
încrucișezi pe toate, sortezi una și cauți binar în ea.
Identitatea din spatele întregii tehnici: 2^n = 2^(n/2) * 2^(n/2). Explozia
exponențială e un PRODUS al celor două jumătăți — dar tu nu ești obligat să
plătești produsul. Enumerarea separată costă doar SUMA, 2 * 2^(n/2), adică
radical din 2^n. Singura condiție: combinarea celor două liste să rămână
ieftină (sortare + căutare binară, nu încrucișare totală) — altfel produsul
reapare pe ușa din spate.
Ca să găsesc o submulțime cu suma S dintre n elemente, încerc toate cele
2^n submulțimi: pentru fiecare, calculez suma și verific dacă e S. Simplu și
corect.
La n = 40 avem 2^40, adică aproximativ 10^12 submulțimi — peste o mie de
miliarde. Chiar și la un miliard de operații pe secundă, asta înseamnă peste
1000 de secunde. Forța brută explodează exponențial și ia TLE.
Împart cele n elemente în DOUĂ jumătăți de câte n/2. Generez toate cele
2^(n/2) sume ale fiecărei jumătăți — la n = 40 înseamnă doar 2^20, adică
aproximativ 10^6 (un milion) de sume per jumătate, nu un trilion. Apoi, pentru
fiecare sumă s din prima jumătate, îmi trebuie o sumă egală cu S - s în a
doua jumătate; o caut binar în a doua jumătate sortată. Costul devine
2^(n/2) * log în loc de 2^n — un milion de căutări rapide, nu un trilion de
verificări.
Generez sumele primei jumătăți și sumele celei de-a doua. Sortez a doua listă de
sume. Pentru fiecare sumă s din prima, caut binar valoarea S - s în a doua.
Dacă o găsesc, există o submulțime cu suma S.