h2. Scurta descriere a unei solutii $O(N logN)$ la 'problemele':problema/naveplanare 'Nave':problema/nave_interdimensionale
In sursa 'aceasta':job_detail/2653120?action=view-source am rezumat felul in care arata reteaua de flux pe care o descrie, de fapt, problema. Imaginea se afla intre liniile $164$ si $173$. Faptul ca o retea de flux maxim de cost minim modeleaza cerinta inseamna ca indeplinim conditiile de convexitate cerute de cele ce urmeaza:
 
==include(page="descriere/nave/lucian-hint1")==

==include(page="nave-lucian-hint1")==

---

Prin urmare, cautam binar cel mai mare $lambda$ pentru care numarul minim (notat cu $cnt$) de unitati de flux trimise _direct_ la Destinatie, intr-o solutie de cost minim, este mai mic sau egal cu acel numar $K$ dat. Problema se poate rezolva intr-un mod asemanator si daca am vrea sa-l maximizam pe $cnt$ si sa facem cautarea binara putin pe dos, si puteti studia diferentele intre cele doua surse.
 
 
==include(page="descriere/nave/lucian-hint2")==

==include(page="nave-lucian-hint2")==

---

Vom folosi programare dinamica si vom avea grija sa obtinem, in caz de egalitate dupa cost, numarul minim de unitati de flux.
 
 
==include(page="descriere/nave/lucian-hint3")==
 
 
==include(page="descriere/nave/lucian-hint4")==
 
 
==include(page="descriere/nave/lucian-hint5")==

==include(page="nave-lucian-hint3")==

---

!descriere/nave/prea-usor?Type1.jpg!
 
In imaginea de mai sus puteti vedea cum se schimba graficul in timpul operatiei de tip $1$. Practic, segmentul care intersecteaza pozitia $0$ este sectionat, intrucat trebuie sa notam ca acolo este o dubla schimbare de panta.
 
!descriere/nave/prea-usor?Type2.jpg!
 
In aceasta imagine puteti vedea cum se schimba graficul in timpul operatiei de tip $2$. Tot ce se intampla e ca in dreptul minimului este inserat un segment de lungime $1$ si panta $0$, partea din dreapta a graficului "mutandu-se" cu o pozitie mai la dreapta, iar cea din stanga ramanand intacta. De asemenea, de retinut ca toate valorile din dreapta minimului nu doar ca si-au schimbat, prin aceasta operatie, valoarea din $dp[]$, ci chiar si acea valoare $cnt$ (care ne spune cate unitati de flux merg direct la Destinatie) este incrementata!
 
Operatia de tip $3$ inseamna sa scadem panta ultimului segment, iar operatia $4$ este o simpla shiftare a graficului cu $input[i+1]$ pozitii pe $Ox$.
 
 
==include(page="descriere/nave/lucian-hint6")==

==include(page="nave-lucian-hint4")==

---

Bucla critica (cea care da complexitatea) este data de numarul de pasi pe care ii fac ce doi iteratori. In primul rand, vedem ca: operatia $1$ schimba panta, adica afecteaza pozitionarea iteratorului $(2)$; operatia $2$ poate schimba pozitiile celor doi iteratori cu cate $1$ - intuitiv, nu e tocmai ingrijorator; operatia $3$ nu ii afecteaza deloc pe iteratori; operatia $4$ schimba pozitia iteratorului $(2)$ cu $input[i+1]$. Deoarece aceasta se intampla intr-un singur sens, si fiecare segment intalnit are lungime cel putin $1$, e clar ca plimbarea lui $(1)$ va consta in schimbarea de $O(N)$ ori a nodului catre care indica.
 
Intrucat nu putem comprima cu usurinta segmente consecutive care pastreaza panta, pentru ca ele retin informatii legate de $cnt$, la prima vedere, am putea spune ca exista teste pe care comportamentul sa fie patratic: schimbarea pantei, fie ea cu $1$ numai, poate influenta pozitionarea iteratorului $(2)$ in asa fel incat sa trebuiasca sa parcurga, dus si intors, de mii de ori, un mare lant de segmente care nu ii schimba panta.

==include(page="nave-lucian-hint5")==

Cheia se afla in faptul ca operatia $1$ il atrage practic pe iteratorul $(2)$ inspre $(1)$, oriunde s-ar afla. E clar ca pana ajunge in preajma lui $(1)$, nu poate parcurge mai multe noduri decat cate sunt in total intre cei doi - in total $O(N)$ de-a lungul algoritmului. Dar ce se intampla daca in preajma lui $(1)$ se va "invarti" in jurului lui si ca parcurge adesea mari multimi de segmente egale? Marile multimi acestea nu pot exista, intrucat felul in care se comporta succesiunea operatiilor $1$ si $2$, ca sa nu mai vorbim si de $4$, face in asa fel incat, daca cei doi iteratori sunt aproape unul de altul, segmentele consecutive sa aibe pante diferite.
 
Cat despre minimizarea (maximizarea) lui $cnt$, vom face actiona pe doua planuri, pentru a simula corect desfasurarea etapelor din programarea dinamica obisnuita:

---

* in cadrul operatiei de tip $2$, vom insera segmentul cat mai la dreapta (stanga) valorilor minime din sir
* la finalul operatiei de tip $3$, vom sterge (ne vom abtine din a sterge) toate segmentele de panta $lambda$, mai putin pe primul (cel mai la stanga), a carui lungime, o fixam ca fiind $infinit$

==include(page="nave-lucian-hint6")==

*In concluzie*, am putea rezuma solutia aceasta ca: smenul de la Aliens + optimizare de dinamica cu slope trick / mentinerea celei de-a doua derivate discrete + liste dublu inlantuite.