h1(#heist). 'Soluţia':jc2020/solutii/heist problemei 'Heist':problema/heist

h1. 'Soluţia':jc2020/solutii/heist problemei 'Heist':problema/heist

Prima observaţie importantă este că <tex> !(a\ \oplus\ expresie)\ = \ !a\ \oplus\ expresie\ = \ a\ \oplus\ !expresie </tex> si ca <tex>!a\ \oplus\ !b\ =\ a\ \oplus\ b</tex>. 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 <tex>a\ \oplus\ a =\ 0\ </tex>, 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 <tex>N</tex> variabile în care putem avea maxim un semn de negaţie. În total sunt <tex>2^{(n+1)}</tex> astfel de expresii deci dacă le-am genera pe toate şi le-am evalua cu un backtracking, complexitatea finală ar fi <tex>O(2^{(2*n+1)})</tex>, o soluţie care dacă este suficient de bine optimizată poate să ia $60$ de puncte.

Cum operaţia xor e asociativă şi comutativă şi <tex>a\ \oplus\ a =\ 0\ </tex>, putem scrie orice expresie fara paranteze si fiecare variabila sa apara fie o data, fie deloc. Astfel singurele expresii pe care trebuie sa le luam in considerare sunt cele cu maxim <tex> n </tex> variabile in care putem avea maxim un semn de negatie. In total sunt <tex>2^{(n+1)}</tex> astfel de expresii deci daca le-am genera pe toate si le-am evalua cu un backtracking, complexitatea finala ar fi <tex>O(2^{(2*n+1)})</tex>, o solutie care daca este suficient de bine optimizata poate sa ia $60$ de puncte.

Ne dăm seama că dacă pe prima poziţie din şirul de biţi apare <tex>1</tex>, atunci semnul de negaţie apare neapărat. La fel dacă pe prima poziţie din şirul de biţi apare <tex>0</tex>, atunci nu avem semn de negaţie. Astfel putem determina în <tex>O(1)</tex> 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.

Ne dam seama ca daca pe prima pozitie din sirul de biti apare $1$, atunci semnul de negatie apare neaparat. La fel daca pe prima pozitie din sirul de biti apare $0$, atunci nu avem semn de negatie. Astfel putem determina in <tex>O(1)</tex> daca avem negatie sau nu. Daca avem negatie, putem nega intreg sirul de biti si putem rezolva problema la fel ca in cazul in care nu avem negatie.

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

Daca indexam sirul de biti de la $0$, stim ca bitul de pe pozitia <tex>2^i</tex>, unde <tex>0 \le i \le n</tex>, ii corespunde valorii expresiei atunci cand toate variabilele mai putin variabila cu ordinul <tex>(n\ -\ i)</tex> sunt egale cu $0$. Daca bitul de pe pozitia <tex>2^i</tex> are valoarea $0$ inseamna ca variabila nu apare in expresie, iar daca are valoarea $1$ inseamna ca variabila apare in expresie. Astfel am determinat in <tex>O(n)</tex> o expresie posibil valida. Trebuie sa verificam daca expresia determinata este corecta, asta fiind foarte usor cu un backtracking in <tex>O(2^n)</tex>, o solutie de complexitate <tex>O(2^n)</tex> obtinand $100$ de puncte.

protected

private