Solutia problemei Silvania

Multumim lui MatteoalexandruMatteo Verzotti •Matteoalexandru pentru editorial!

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.

Solutie N3 * log(N) - ~20 puncte

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 = \displaystyle \sum_{x=1}^{i-1} lemn[x] + \sum_{y = j + 1}^{n} lemn[y].
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.

Solutie N3 - ~20 puncte

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.

Solutie N2 * log(N) - 100 puncte

Se va proceda la fel ca la solutia precedenta, insa se va folosi o structura de date numita heap . Aceasta structura de date ne va permite sa inseram si sa stergem elementul curent in complexitate O(log(N)).

Solutie N2 - 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 ≤ j), care la inceput vor fi amandoi 1. Astfel, daca lemn[j] ≤ 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(N2), care va lua punctaj maxim.

OBSERVATIE: lmax nu poate fi cautat binar.