!problema/lca?arbore.gif 80%!
O primă soluţie, care caută între toate nodurile arborelui şi îl reţine pe cel care strămoş al ambelor noduri din întrebare, având complexitatea fi nală <tex>O(N*M)</tex> ar trebui să obţină ... puncte şi se găseşte 'aici':...
O primă soluţie, care caută între toate nodurile arborelui şi îl reţine pe cel care strămoş al ambelor noduri din întrebare, având complexitatea fi nală <tex>O(N*M)</tex> ar trebui să obţină 20 puncte şi se găseşte 'aici':...
O altă soluţie descrisă în 'acest articol':multe-smenuri-de-programare-in-cc-si-nu-numai având complexitatea finală de <tex>O(N + M\sqrt{N})</tex> ar trebui să obţină ... puncte. 'Aici':... se găseşte o sursă care se bazează pe această idee.
O soluţie relativ uşor şi rapid de implementat în condiţii de concurs este cea care foloseşte ideea de la problema 'Strămoşi':problema/stramosi. Se reţine pentru fiecare nod, strămoşul cu <tex>2^{k}</tex> nivele mai sus, unde $k$ ia valori între <tex>1</tex> şi <tex>log_{2}N</tex>. Astfel, pentru fiecare query, la început se aduce nodul de pe nivelul mai mare pe acelaşi nivel cu celalt, iar apoi, se poate afla în timp logaritmic $LCA$-ul celor două noduri. Această soluţie ar trebui să obţină ... puncte, iar sursa care se bazează pe această idee este 'aceasta':...
O soluţie relativ uşor şi rapid de implementat în condiţii de concurs este cea care foloseşte ideea de la problema 'Strămoşi':problema/stramosi. Se reţine pentru fiecare nod, strămoşul cu <tex>2^{k}</tex> nivele mai sus, unde $k$ ia valori între <tex>1</tex> şi <tex>log_{2}N</tex>. Astfel, pentru fiecare query, la început se aduce nodul de pe nivelul mai mare pe acelaşi nivel cu celalt, iar apoi, se poate afla în timp logaritmic $LCA$-ul celor două noduri. Complexitatea finală este <tex>O(Nlog_{2}N + Mlog_{2}N)</tex>Această soluţie ar trebui să obţină ... puncte, iar sursa care se bazează pe această idee este 'aceasta':...
Soluţia care ar trebui să obţină 100 de puncte se bazează pe următoarea observaţie: $LCA$-ul a $2$ noduri este nodul de nivel maxim dintre primele apariţii ale nodurilor din întrebare din reprezentarea Euler a arborelui. în cazul de faţă, reprezentarea Euler a arborelui este următoarea, iar pe următorul rând sunt nivelurile nodurilor:
$1 2 4 7 4 8 4 2 5 2 6 9 6 2 1 3 10 3 11 3 1$
Soluţia care ar trebui să obţină 100 de puncte se bazează pe următoarea observaţie: $LCA$-ul a $2$ noduri este nodul de nivel minim dintre primele apariţii ale nodurilor din întrebare din reprezentarea Euler a arborelui. în cazul de faţă, reprezentarea Euler a arborelui este următoarea, iar pe următorul rând sunt nivelurile nodurilor:
De exemplu, pentru nodurile $8$ şi $9$, răspunsul este nodul cu nivel maxim din secvenţa $8 4 2 5 2 6 9$, mai exact nodul 2.
table{width:700px; text-align:center;}.
|_. $reprezentarea Euler$| $1$ | $2$ | $4$ | $7$ | $4$ | $8$ | $4$ | $2$ | $5$ | $2$ | $6$ | $9$ | $6$ | $2$ | $1$ | $3$ | $10$ | $3$ | $11$ | $3$ | $1$ |
|_. $nivelul$ | $0$ | $1$ | $2$ | $3$ | $2$ | $3$ | $2$ | $1$ | $2$ | $1$ | $2$ | $3$ | $2$ | $1$ | $0$ | $1$ | $2$ | $1$ | $2$ | $1$ | $0$ |
De exemplu, pentru nodurile $8$ şi $9$, răspunsul este nodul cu nivel minim din secvenţa $8 4 2 5 2 6 9$, mai exact nodul 2, care are nivelul $1$.
Pentru a implementa această soluţie, se folososesc arbori de intervale, având complexitatea <tex>O(N + Mlog_{2}N)</tex>, soluţie care ar trebui sa obţină ... de puncte, sursa care se bazează pe acest principiu fiind 'aceasta':....
Mai eficient, pentru determinarea minimului unei subsecvenţe se poate folosi 'RMQ':problema/rmq. Astfel, complexitatea finală va fi <tex>O(Nlog_{2}N + M)</tex>, aceasta soluţie obţinând 100 de puncte, sursa care se bazează pe această idee se găseşte 'aici':...
== include(page="template/taskfooter" task_id="lca") ==
