Revizia anterioară Revizia următoare
Scurta descriere a unei solutii O(N logN) la problemele Nave
In sursa aceasta 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
---
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.
--- Indiciul 2
---
Vom folosi programare dinamica si vom avea grija sa obtinem, in caz de egalitate dupa cost, numarul minim de unitati de flux.
--- Indiciul 3
--- Indiciul 4
--- Indiciul 5
---
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.
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.
--- Indiciul 6
---
Bucla critica (cea care da complexitatea) este data de numarul de pasi pe care ii fac ce doi iteratori:
- (1)
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.
