h2. Scurta descriere a unei solutii $O(N logN)$ la 'problemele':problema/naveplanare 'Nave':problema/nave-interdimensionale

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:
--- Indiciul 1

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

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

---

--- Indiciul 2

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

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

---

--- Indiciul 3

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

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

--- Indiciul 4

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

==include(page="descriere/nave/lucian-hint4")==
 
--- Indiciul 5
 
==include(page="descriere/nave/lucian-hint5")==

---

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

!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$.
 
--- Indiciul 6
 
==include(page="descriere/nave/lucian-hint6")==

---

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

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.
 
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$

*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.