2
|

!> problema/lca?arbore.gif 50%!
 

h3. Explicaţie

Arborele din exemplu arată astfel:

Arborele din exemplu arată ca în figura alăturată...

!< problema/lca?arbore.gif 70%!

h2. Indicaţii de rezolvare

O primă 'soluţie':job_detail/368458?action=view-source, care caută LCA-ul celor două noduri mergând "în sus" pe ramurile nodurilor până când acestea se intersectează, având complexitatea de <tex>O(N*M)</tex>, ar trebui să obţină $30$ puncte.

Pentru exemplificare, nodurile $8$ şi $9$ au cel mai apropiat strămoş comun nodul cu nivel minim din secvenţa $8 4 2 5 2 6 9$, adică nodul $2$, care are nivelul $1$. Pentru a implementa această soluţie, putem folosi 'arbori de intervale':problema/arbint, având complexitatea <tex>O(N + Mlog_{2}N)</tex>, 'soluţie':job_detail/368434?action=view-source care ar trebui să obţină $70$ de puncte. Mai eficient, ţinând cont de restricţiile problemei, pentru determinarea minimului unei subsecvenţe se poate folosi 'RMQ':problema/rmq. Astfel, complexitatea finală va fi <tex>O(Nlog_{2}N + M)</tex>, această 'soluţie':job_detail/368469?action=view-source obţinând $100$ de puncte. Dezavantajul acestei metode constă în faptul că se foloseşte <tex>O(Nlog_{2}N)</tex> memorie, ceea ce poate fi un impediment în anumite cazuri.

Un articol ce explică foarte bine atât RMQ, cât şi LCA se găseşte pe 'TopCoder':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor.

Un articol ce explică foarte bine atât RMQ, cât şi LCA se găseşte pe 'TopCoder':https://www.topcoder.com/community/data-science/data-science-tutorials/range-minimum-query-and-lowest-common-ancestor/.

h3. Aplicaţii

h2. Aplicaţii

* 'CT':problema/ct
* 'Atac':problema/atac

* 'Pirati':problema/pirati

* 'Concurs':problema/concurs
* 'Delay':problema/delay
* 'Radiatie':problema/radiatie