Soluţia problemei Heist

Prima observaţie importantă este că si ca . Aşadar ne dăm seama că orice expresie poate fi rescrisă fără semne de negaţie sau cu un singur semn de negaţie, în funcţie de paritatea numărului semnelor de negaţie care apar în expresia iniţială.

Cum operaţia xor e asociativă şi comutativă şi , putem scrie orice expresie fără paranteze şi fiecare variabilă să apară fie o dată, fie deloc. Astfel singurele expresii pe care trebuie să le luăm în considerare sunt cele cu maxim variabile în care putem avea maxim un semn de negaţie. În total sunt astfel de expresii deci dacă le-am genera pe toate şi le-am evalua cu un backtracking, complexitatea finală ar fi , o soluţie care dacă este suficient de bine optimizată poate să ia 60 de puncte.

Ne dăm seama că dacă pe prima poziţie din şirul de biţi apare , atunci semnul de negaţie apare neapărat. La fel dacă pe prima poziţie din şirul de biţi apare , atunci nu avem semn de negaţie. Astfel putem determina în dacă avem negaţie sau nu. Dacă avem negaţie, putem nega întreg şirul de biţi şi putem rezolva problema la fel ca în cazul în care nu avem negaţie. Mai departe rezolvăm problema când nu avem negaţie.

Dacă indexăm şirul de biţi de la , ştim că bitul de pe poziţia , unde , îi corespunde valorii expresiei atunci când toate variabilele mai puţin variabila cu ordinul sunt egale cu . Dacă bitul de pe poziţia are valoarea înseamnă că variabila nu apare în expresie, iar dacă are valoarea înseamnă că variabila apare în expresie. Astfel am determinat în o expresie posibil validă. Trebuie să verificăm dacă expresia determinată este corecta, asta fiind foarte uşor cu un backtracking de complexitate , soluţie care obţine 100 de puncte.