Noi vom intersecta mereu o multime de intervale cu un interval de forma (x-D,x+D) care se va transpune in 1 sau 2 intervale necirculare, adica Y[i].size() va fi mereu 1 sau 2. Complexitatea functiei de mai sus este astfel <tex>O(N*M)</tex>.

Acum, modul in care vom parcurge intersectiile va dicta complexitatea finala. Daca pur si simplu iteram prin cele 2^M configuratii iar pentru fiecare configuratie construim intersectia intervalelor din configuratie de la 0, complexitatea va fi <tex>O(N*M^2^*2^M^)</tex>.

Acum, modul in care vom parcurge intersectiile va dicta complexitatea finala. Daca pur si simplu iteram prin cele 2^M configuratii iar pentru fiecare configuratie construim intersectia intervalelor din configuratie de la zero, complexitatea va fi <tex>O(N*M^2^*2^M^)</tex>.

Complexitatea care rezolva problema este <tex>O(N*M*2^M^)</tex> care poate fi obtinuta prin metoda backtracking: Construim treptat intersectia si mentinem o stiva cu starea intersectiilor la fiecare pas. La pasul pasul i alegem daca sa adaugam sau nu al i-lea cod din cele M la configuratia curenta. Daca nu-l adaugam, cream un nou nivel pe stiva in care starea intersectiilor este aceeasi. Daca il adaugam, cream un nou nivel pe stiva in care starea intersectiilor este rezultatul apelarii functiei _intersect_(starea curenta, al i-lea cod). In ambele cazuri trecem la pasul i+1 iar cand ne intoarcem avem salvata pe stiva starea de la care am plecat. Costul tranzitionarii de la un pas la altul este <tex>O(N*M)</tex> si vom trece prin <tex>O(2^M)</tex> pasi.

Complexitatea care rezolva problema este <tex>O(N*M*2^M^)</tex> care poate fi obtinuta prin metoda backtracking, construind treptat intersectia celor M coduri.

==include(page="onis-2015/solutii-runda-1/invazia")==