Pagini recente » Easy Query | Requeim for a dream... | Emax | Autentificare | Diferente pentru onis-2015/solutii-runda-1 intre reviziile 58 si 57
Nu exista diferente intre titluri.
Diferente intre continut:
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 zero, 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 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, construind treptat intersectia celor M coduri.
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.
==include(page="onis-2015/solutii-runda-1/invazia")==
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.