PROBLEMA 33: Din mosi-stramosi
DEADLINE: Marti, 19 octombrie
DOMENIU: Arbori (am o obsesie)
TIMP DE IMPLEMENTARE: 2h (pentru cine lucreaza pe Sparc, 20h)
PUNCTAJ: 100 dexteri
Problema are o forma mai ciudata. Ar fi trebuit sa va furnizez un modul,
dar in momentul de fata imi este cam greu, asa ca am gasit o alta solutie.
Cititi-o cu atentie si sa speram ca o sa va lamuriti.
O prima varianta a problemei spune asa. Se da un arbore cu radacina, cu
N<=5.000 noduri numerotate de la 0 la N-1. Se mai dau M<=10.000 perechi
de noduri. Pentru fiecare din aceste perechi se cere sa se indice "Cel mai
recent stramos comun", adica un nod cat mai departat de radacina, care sa le
fie stramos ambelor noduri din pereche. Vom nota acest nod cu LCA(X, Y), de
la denumirea englezeasca "Lowest Common Ancestor". Se poate considera ca un
nod este propriul lui stramos :) Un nod poate aparea in mai multe perechi.
Exemplu: Se da arborele din figura.
5 Atunci:
/ | \ LCA(2, 4)=5
2 3 0 LCA(4, 6)=3
/ \ LCA(3, 6)=3
1 4 LCA(6, 3)=3
| LCA(2, 2)=2
6
In cazul "offline" in care se cunosc de la inceput toate cele M perechi,
propun ca tema pentru acasa sa gasiti un algoritm O((M+N) log* N). Noi
ne vom ocupa de cazul mai interesant al aceluiasi algoritm "online" in care
perechile vi se dau pe rand si trebuie sa dati raspunsul pentru o pereche
inainte de a o primi pe urmatoarea.
Si acum vine magaria pe care am facut-o. Daca va dadeam toate cele M perechi
in fisierul de intrare, nu va puteam forta sa le procesati una cate una -
le puteati incarca pe toate. Deci iata ce am nascocit. In fisierul de
intrare vi se vor da sase numere, A, B, C, D, X si Y. X si Y sunt
prima pereche de noduri careia trebuie sa-i gasiti LCA(X,Y). Fie acesta Z.
Pentru a afla urmatoarea pereche, veti calcula:
X'=(A*X+B*Y) mod N
Y'=(C*Y+D*Z) mod N
Veti raspunde si la aceasta intrebare, fie Z'=LCA(X',Y'), apoi veti
calcula:
X"=(A*X'+B*Y') mod N
Y"=(C*Y'+D*Z') mod N
Si asa mai departe, pana veti da M raspunsuri. Deci trebuie sa dati
raspunsul la o pereche pentru a o afla pe urmatoarea, din cauza ca Z
intervine in calculul lui Y', Z' intervine in calculul lui Y" etc.
DATE DE INTRARE: Fisierul text STRAMOS.IN contine datele sub forma:
N M ; N si M :)
T0 T2 ... T(N-1) ; Ti = tatal nodului i (sau -1 daca i este radacina)
X Y ; Prima pereche pentru care se cere LCA(X,Y)
A B C D ; Coeficientii pentru a afla urmatoarea pereche
(0 < A, B, C, D < N)
DATE DE IESIRE:
Fisierul de iesire STRAMOS.OUT va contine M numere separate prin spatii,
respectiv pentru fiecare din cele M perechi se va tipari cel mai recent
stramos comun.
EXEMPLU: (pentru figura de mai sus)
STRAMOS.IN STRAMOS.OUT
7 10 3 5 1 5 3 5 5 5 1 1
5 3 5 5 3 -1 1
1 4
1 2 3 4
TIMP DE RULARE: O secunda, o secunda, eu l-am fost zarit in unda :)
COMPLEXITATE RECOMANDATA: O(M log N + N log N), sau O(M log N + N)
pentru cine are un pic de rabdare si timp.
OBSERVATII:
1) log* N se defineste ca "numarul minim x pentru care log log ... logN<1"
(logaritmul se aplica de x ori). De exemplu, log* 16 = 4, pentru ca
log log log log 16 = 0, log* 2^16=5, log* 2^(2^16)=6. Remarcati ca
functia
log* poate fi practic asimilata cu O(1), pentru ca niciodata nu va fi
mai mare
ca 6. Numai teoreticienii astia inraiti de aici nu o considera O(1) :)
2) Verificati cu grija exemplul, ca sa nu pierdeti puncte din cauza
iteratiilor
pe care va oblig sa le faceti.
3) Iteratia nu va cicla, deci nu va bazati pe faptul ca va voi pune sa
calculati de 10.000 ori raspunsul pentru aceeasi pereche sau altceva de
genul acesta :)
|
|
