Solutii FMI No Stress 3

fmi-no-stress-3/solutii

Problema cere sa găsim un arbore binar având la dispoziţie parcurgerile lui inordine şi preordine. Parcurgerea inordine este: $STÂNGA RĂDĂCINA DREAPTA$ iar cea în preordine este $RĂDĂCINA STÂNGA DREAPTA$.

Precalculând pentru fiecare nod care este poziţia sa din parcurgerea în inordine, putem rezolva problema în timp liniar, folosind o funcţie recursiva. Iniţial ştim ca rădăcina este primul nod din parcurgerea în preordine. O cautam în parcurgerea inordine. Acum fiul stâng al rădăcinii este subarborele cu parcurgerea în inordine intre indicii $1$ şi $X-1$, iar fiul drept este subarborele cu parcurgerea în inordine intre indicii $X+1$ şi $N$. Apelam funcţia mai departe şi pentru cei doi fii, în aceasta ordine, pentru a ştii la al câtelea nod suntem din parcurgerea în preordine.

Precalculând pentru fiecare nod care este poziţia sa din parcurgerea în inordine, putem rezolva problema în timp liniar, folosind o funcţie recursiva. Iniţial ştim ca rădăcina este primul nod din parcurgerea în preordine. O cautam în parcurgerea inordine. Acum fiul stâng al rădăcinii este subarborele cu parcurgerea în inordine intre indicii $1 şi $X-1$, iar fiul drept este subarborele cu parcurgerea în inordine intre indicii $X+1$ şi $N$. Apelam funcţia mai departe şi pentru cei doi fii, în aceasta ordine, pentru a ştii la al câtelea nod suntem din parcurgerea în preordine.

== code(cpp) |
void construct (int left,int right,node* &root) {

Y = 2 * (B[i] - A[i]);
Vor aparea astfel ecuatii de forma: T = X1 + K * Y si T = X2 + K * Y, unde T reprezinta un timp ce nu poate constitui o solutie, iar K este un numar natural.
Vom marca aceste ecuatii cu ajutorul unui map care ne va ajuta sa nu avem ecuatii redundante. Astfel pentru fiecare Y, vom tine maxim Y ecuatii.

La fiecare pas la care descoperim o ecuatie noua, eliminam timpii care nu pot constitui o solutie utilizand un algoritm asemanator ciurului lui Eratostene. Pentru a gasi solutia parcurgem toti timpii de la 0 la 200000 si il gasim pe cel mai mic care a ramas nemarcat in urma ciurului.
Complexitate: O(N sqrt N)

La fiecare pas la care descoperim o ecuatie noua, eliminam timpii care nu pot constitui o solutie utilizand un algoritm asemanator ciurului lui Eratostene. Pentru a gasi solutia parcurgem toti timpii de la 0 la 200000 si il gasim pe cel mai mic care a ramas nemarcat in urma ciurului.