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) {

h2. 'Meneaito':problema/meneaito
Se observa ca pentru ca un timp sa reprezinte o solutie, atunci pentru fiecare coloana i, 1 < i < N, dansatorul de pe coloana i trebuie sa nu fie pe pozitia i. Astfel, putem marca timpii in care pe o anumita coloana i, pozitia i este ocupata. Mentionam ca nu ne intereseaza cazul in care i < A[i] sau i > B[i]. Pentru celelalte cazuri(unde A[i] <= i <= B[i]), consideram 2 posibilitati:

1) Dansatorul se afla pe pozitia i si se indreapta in jos;
2) Dansatorul se afla pe pozitia i si se indreapta in sus;

1) Dansatorul se afla pe pozitia i si se indreapta in jos
2) Dansatorul se afla pe pozitia i si se indreapta in sus

Observam ca pentru fiecare dintre aceste cazuri avem un timp(notat X1 pentru primul caz si X2 pentru al doilea caz) cand evenimentul se produce prima data. Deasemenea observam ca evenimentul(aparitia unui timp care nu poate fi solutie) se produce la un interval dat de timp, notat in continuare Y.
Se vede usor faptul ca:

X1 = i - A[i];
X2 = 2 * (B[i] - i) - (A[i] - i);
Y = 2 * (B[i] - A[i]);

X1 = i - A[i]
X2 = 2 * (B[i] - i) - (A[i] - i)
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