872 Matrice 2

[•DITzoneC]

Aici puteţi discuta despre problema Matrice 2.

[•ciprianf]

Am si eu o intrebare. Am citit articolul cu solutii dar nu prea inteleg ce vrea sa zica prin

Cod:

 De aceea, pentru fiecare din cele Q query-uri vom cauta rezultatele binar in paralel

Cum adica in paralel? Cum ar trebui sa fac?

[•SebiSebi]

Salut!
Îmi poate explica cineva la ce se referă cele 2 căutări binare în paralel din soluția oficiala?

[•florin.elfus]

Pentru inceput sa zicem ca rezolvi fiecare query independent. Trebuie sa alegi un drum astfel incat valoarea minima a drumului intre (x1, y1) si (x2, y2) sa fie maxima. Sa zicem ca valoarea minima a unui drum este X. Atunci exista un drum intre (x1, y1) si (x2, y2) cu toate valorile >= X. Observi ca daca exista un drum cu toate valorile >= X, va exista un drum cu toate valorile >= X - 1. Asa ca pentru a afla maximul, poti folosi cautarea binara. E important sa folosesti cautarea binara a lui Patrascu, cu puteri ale lui 2.

Cum determini daca o valoare X e buna ca raspuns? O solutie posibila (care va ajuta la cautarea binara in paralel) este sa consideri initial fiecare celula ca fiind o multime disjuncta separata. Cand gasesti o celula cu valoare >= X iei fiecare din cei 4 vecini ai ei. Daca vecinul are si el valoare >= X vei uni multimea disjuncta a celulei cu cea a vecinului. X este bun ca raspuns daca (x1, y1) si (x2, y2) se afla in aceeasi multime disjuncta.

Acum folosim cautarea binara a lui Patrascu. Sa zicem ca am incercat deja puterile {19, 18, ..., i + 1} iar acum incercam puterea 2 ^ i. Daca raspunsurile pana acum au fost {X1, X2, ..., XQ} acum raspunsurile vor fi {X1 + 2 ^ i, X2 + 2 ^ i, ..., XQ + 2 ^ i}. Trebuie sa determinam pentru fiecare din valorile astea noi daca e un raspuns bun. Daca e, vom adauga 2 ^ i la ea. Daca nu, nu vom adauga.

Am redus problema la a raspunde la Q intrebari de forma: (x0, y0, x1, y1, val): exista un drum intre (x0, y0) si (x1, y1) cu toate numerele >= val?  Putem rezolva online fiecare query, dar nu castigam nimic fata de solutia brute. Ideea e sa gasim un algoritm offline, adica sa raspundem la intrebari intr-o ordine avantajoasa.

Sortam toate cele Q intrebari dupa valoarea val, in ordine descrescatoare. Acum, sa zicem ca am raspuns la primele i query-uri. Folosim metoda de mai sus, cu multimi disjuncte. In multimea disjuncta vor fi unite toate nr cu valori >= val_i . Pentru query-ul i + 1 stiu ca val_(i + 1) <= val_i . De asemenea, stiu ca toate numerele >= val_i sunt deja in multimea disjuncta. Deci, mai trebuie unite doar numerele cuprinse intre val_(i + 1) si val_i. Daca am sorta si valorile initiale ale matricei descrescator, ne putem plimba cu un pointer pe sirul valorilor si sa adaugam fiecare valoare o singura data in multimea disjuncta. Fiecare valoare e adaugata o singura data, deci se fac N ^ 2 modificari pe multimea disjuncta pt fiecare 2 ^ i. Deci obtii O((N ^ 2 * log* N + Q) * logN).

[•SebiSebi]

MulÈ›umesc pentru explicaÈ›ie!   

[•retrograd]

Solutia mea (care tin sa mentionez ca iese din memorie) se bazeaza pe ideea construirii unui graf si sortarii muchiilor descrescator dupa cost (egal cu minimul intre valorile citite pentru extremitati). Dupa ce le-am sortat, iau si unesc cele doua paduri pe care le am eu, si in paralel imi construiesc un arbore la care un nod nou se leaga de nodurile ambelor paduri :

Cod:

pentru fiecare muchie
   daca padurea lui i != padurea lui j
      creez un nou nod
      nodul nou creat il leg de nodul ambelor paduri
      fac reuniune din paduri si actualizez nodul reuniunii cu nodul nou creat
      retin in VAL[nod] costul muchiei curente ("nod" e noul nod creat)

Acum, arborele meu arata ca un min heap (fiecare nod are doi fii, cu valori asociate mai mari), iar aflarea solutie pentru doua coordonate este fix valoarea asociata lca-ului celor doua noduri.

Exista o metoda sa fac lca-ul a doua noduri in timp util (logaritmic, de preferabil) in cat mai putina memorie, avand in vedere faptul ca arborele este binar? (chiar si un arbore de intervale are nevoie de ~O(12*nr_nod) memorie, unde nr_nod sunt numarul de noduri ale arborelui creat, egal cu 2*n*n, iar limita e cam mica ).

[•retrograd]

Update : Aparent am luat suta cu un algoritm "naiv" pentru lca (bazat pe adancimi). Se pare ca nu sunt teste la care sa imi dea TLE. Ciudat...