Dar stati, complexitatea nu devine cumva <tex>O(Nr.aparitii^2^)</tex> ? De fapt, fiecare interval este parcurs si updatat atata timp cat el contine pozitia curenta. Intervalele sunt de lungime maxim 100 si complexitatea acestei parti este de fapt <tex>O(N + Nr.aparitii*L)</tex>.
Tinem sa-l felicitam pe ==User(user="andreiiii" type="tiny")==, care a reusit sa rezolve aceasta problema specataculos in ultimul minut.

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

Solutia la aceasta problema se foloseste de 'principiul includerii si excluderii':http://www.infoarena.ro/problema/pinex. Vom numara si aduna numarul de coduri care deschid seiful datorita apropierii de primul cod din cele $M$, de a al doilea cod, de al treilea cod.. apoi le vom scadea pe cele care sunt apropiate simultan de primul si al doilea, de primul si de al treilea, de al doilea si de al treilea.. etc.
 
Presupunand ca am fixat o configuratie de coduri si stim pe fiecare rotita i @nr[i] = numarul de celule care apartin intersectiei intervalelor corespunzatoare rotitei i@. Numarul de coduri 'apropiate' de fiecare din codurile din configuratie este data de @nr[1]*nr[2]*nr[3]*..nr[N]@.
 
Tot ce trebuie sa facem este construim intersectiile pentru fiecare configuratie, pe fiecare rotita, calculam rezultatul si il adunam sau scadem din solutie.
Lucrul care poate sa nu para evident la prima vedere este ca desi intersectia a $X$ intervale pe o axa este un interval (sau multimea vida), pe un cerc nu este interval. Ea poate consta si din $M$ intervale disjuncte. De exemplu:
----------- -----------
------- ---------------
---- ------------------
 
Cel mai sigur mod de a implementa functia de intersectie este de a ne inchipui ca suntem de fapt pe o axa necirculara. Astfel, intervalele (x,y) cu x > y le despratim in [x,k-1] si [0,y]. Acum, intersectia a X intervale disjuncte cu Y intervale disjuncte este reuniunea intersectiilor fiecare perechi de intervale (a,b) cu a din X si b din Y. Adica functia de intersectie o putem scrie asa:
 
==code(cpp) |
void intersect (vector<pair<int,int> > X[], vector<pair<int,int> > Y[], vector<pair<int,int> > intersection[])
{
    for (int i = 1; i <= n; ++i)  // pentru fiecare rotita
    {
        for (int j = 0; j < X[i].size(); ++j)
        {
            for (int h = 0; h < Y[i].size(); ++h)
            {
                int front = max (X[i][j].first, Y[i][h].first);
                int end = min (X[i][j].second, Y[i][h].second);
 
                if (front <= end)
                    intersection[i].push_back(make_pair(front, end));
            }
        }
    }
}
==
 
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 functie 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>.
 
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 stiv 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.
 

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