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 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, construind treptat intersectia celor M coduri.

*Solutia 1*

La fiecare moment, mentinem liste cu noduri, o lista reprezentand o componenta conexa din graf la acel moment (initial avem N liste a cate un singur element fiecare). In plus, pentru oricare nod retinem carei liste ii apartine si, in cadrul acelei componente conexe, in ce 'echipa' se afla. Daca primim un query intre doua noduri care apartin aceleiasi componente conexe este usor de tratat(NO daca sunt de aceeasi parte, YES daca sunt de parti diferite). Interesant este ce facem daca nodurile sunt din doua componente conexe diferite. Trebuie sa le punem intr-o singura lista cu informatii actualizate. Observam totusi ca nu este nevoie sa ne atingem decat de nodurile uneia din liste. Nodurile dintr-o lista le vom introduce in cealalta lista (lista lor originala o vom elimina) si le vom plasa in 'echipe' relativ la nodurile din aceasta lista. Daca alegem intotdeauna sa mutam nodurile din lista mai mica in lista mai mare, complexitatea va fi <tex>O(M + N*logN)</tex>. Va lasam pe voi sa va ganditi de ce. (indiciu: nodurile vor apartine in final unei singure liste, ganditi-va de cate ori poate fi rmutat un nod pana sa faca parte din lista finala).

La fiecare moment, mentinem liste cu noduri, o lista reprezentand o componenta conexa din graf la acel moment (initial avem N liste a cate un singur element fiecare). In plus, pentru oricare nod retinem carei liste ii apartine si, in cadrul acelei componente conexe, in ce 'echipa' se afla. Daca primim un query intre doua noduri care apartin aceleiasi componente conexe, acesta este usor de tratat(NO daca sunt de aceeasi parte, YES daca sunt de parti diferite). Interesant este ce facem daca nodurile sunt din doua componente conexe diferite. Trebuie sa le punem intr-o singura lista cu informatii actualizate. Observam totusi ca nu este nevoie sa ne atingem decat de nodurile uneia din liste. Nodurile dintr-o lista le vom introduce in cealalta lista (lista lor originala o vom elimina) si le vom plasa in 'echipe' relativ la nodurile din aceasta lista. Daca alegem intotdeauna sa mutam nodurile din lista mai mica in lista mai mare, complexitatea va fi <tex>O(M + N*logN)</tex>. Va lasam pe voi sa va ganditi de ce. (indiciu: nodurile vor apartine in final unei singure liste, ganditi-va de cate ori poate fi mutat un nod pana sa faca parte din lista finala).

*Solutia 2*

* Apare o muchie intre un nod izolat si un nod neizolat. Punem muchia. Nodul neizolat este deja colorat cu o culoare. Coloram nodul izolat cu perechea acestei culori.
* Apare o muchie intre doua noduri neizolate. Daca culorile lor coincid, afisam NO, altfel punem muchia. Sa zicem ca nodurile sunt X si Y iar culoarea lui X este a din perechea de culori (a,b) iar culoarea lui Y este c din perechea de culori (c,d). Vrem sa exprimam ca, de acum in colo, a este echivalent cu d iar b este echivalent cu c. Pentru aceasta putem folosi 'paduri de multimi disjuncte':http://www.infoarena.ro/problema/disjoint.

Complexitatea este <tex>O(N + M*log^*^N)</tex> adica aproximativ <tex>O(N + M)</tex>.

Complexitatea este <tex>O(N + M*log ^* N)</tex> adica aproximativ <tex>O(N + M)</tex>.

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