h1(#silvania). 'Solutia':algoritmiada-2019/runda-finala/solutii/silvania problemei 'Silvania':problema/silvania

h1(#silvania). 'Solutia':algoritmiada-2019/runda-finala/solutii/silvania problemei 'Silvania':problema/silvania
 
Initial, vom folosi 2 vectori:
 
* $lemn[x]$ - cat lemn are copacul de pe pozitia $x$ in vectorul initial
* $poz[x]$ - pe ce pozitie in padure se afla copacul de pe pozitia $x$ in vectorul initial
 
Vom sorta copacii dupa pozitia lor in vectorul $poz$. Acest lucru poate fi facut utilizand un vector de structuri sau de pair.
 
h2. $Solutie N^3^ * log(N)  - 20 puncte (cred)$
 
Vom fixa 2 indici, $i$ si $j$, ({$i$} ≤ $j$) si vom itera cu $i$ de la $1$ la $n$, iar cu $j$ de la $i$ la $n$. In acest moment presupunem ca am taiat toti copacii de la stanga lui $i$ si de la dreapta lui $j$.
Deci lemnul total este $lt$ = <tex> \displaystyle \sum_{x=1}^{i-1} lemn[x] + \sum_{y = j + 1}^{n} lemn[y]</tex>.
Distanta este $dist = poz[j] - poz[i]$. Daca $dist > lt$, atunci vom taia copacii care au cel mai mult lemn cat timp $dist > lt$. Acest lucru poate fi facut sortand intervalul [{$i$},{$j$}] si luand elementele maxime.
 
h2. $Solutie N^3^ - 20 puncte (cred)$
 
Se va proceda la fel ca anterior, insa se vor face 2 observatii:
 
* Daca un copac este taiat, atunci el va ramane taiat pana ce capatul stanga va ajunge la urmatoarea pozitie;
* La fiecare pas, vectorul $lemn$ va avea deja elementele in ordine crescatoare. De aceea putem insera elementul curent in complexitate $O(N)$ si nu va fi necesar sa sortam vectorul din nou.
 
h2. $Solutie N^2^ * log(N) - 100 puncte$
 
Se va proceda la fel ca la solutia precedenta, insa se va folosi o structura de date numita "heap":https://infoarena.ro/heapuri . Aceasta structura de date ne va permite sa inseram si sa stergem elementul curent in complexitate $O(log(N))$.
 
h2. $Solutie N^2^  - 100 puncte$
 
Vom fixa numarul de lemne maxim $lmax$ pe care il putem lua de la un copac, iterand cu el de la $1 la n$. Apoi, pentru fiecare maxim fixat, vom folosi tehnica $2-pointers$. Vom folosi din nou 2 indici, $i$ si $j$, (i &le; j), care la inceput vor fi amandoi $1$. Astfel, daca $lemn[j] &le; lmax$, atunci vom taia copacul $j$. Daca, la un moment dat, distanta dintre $poz[i]$ si $poz[j]$ este mai mare decat lemnul curent, vom creste capatul stanga. Complexitatea tehnicii $2-pointers$ este $O(N)$, ceea ce garanteaza complexitatea finala de $O(N^2^)$, care va lua punctaj maxim.
 
OBSERVATIE: $lmax$ nu poate fi cautat binar.