O alta rezolvare pentru partea a doua, este urmatoarea:
Se pleaca dintr-un punct nemarcat si se marcheaza cu $0$; se merge, pe dreapta, paralel cu $OX$, in urmatorul punct nemarcat, care se marcheaza cu $1$; se merge, apoi, pe dreapta, paralel cu $OY$, in urmatorul punct nemarcat si se marcheaza cu $0$, etc. Pentru o complexitate eficienta, punctele se pot stoca sub forma unor liste, ale caror campuri retin urmatorul punct nemarcat pe $OX$ si, respectiv, urmatorul punct nemarcat pe $OY$. Daca unii utilizatori _InfoArena_, nu sunt obisnuiti cu implementarea listelor, pot tine niste vectori ( $NextOX{~i~}$ si $NextOY{~i~}$ ) in care sa retina indicii urmatoarelor puncte nemarcate.
h2. 'Jetoane2':problema/jetoane2 (problema medie)
h2. 'Jetoane2':problema/jetoane2 (probelma medie)
Problema se rezolva prin programare dinamica. Vom considera $2$ matrici:
Fiind niste limite de timp foarte mari, "cautare binara + flux":http://campion.edu.ro/problems.php?mode=view_solution&problem_id=279&group_number=3&year=2005 nu intra in timp.
Pentru a se incadra in limita stabilita, era necesar algoritmul lui Karzanov pentru flux maxim intr-o retea. Acest algoritm a fost prezentat in cadrul tabereie de pregatire a Lotului National, de catre Mugurel Ionut Andreica ("Algoritmi de flux maxim in retele":http://infoarena.ro/downloads) si constituie o mica parte din teza sa de Masterat.
Pentru a se incadra in limita stabilita, era necesar algoritmul lui Karzanov pentru flux maxim intr-o retea. Acest algoritm a fost prezentat in cadrul taberei de pregatire a Lotului National, de catre Mugurel Ionut Andreica ("Algoritmi de flux maxim in retele":http://infoarena.ro/downloads) si constituie o mica parte din teza sa de Masterat.
Presupunem, intial, ca pe fiecare muchie poate fi plasat +doar un singur soldat+. Cum $S$ < $M$, acest lucru este intotdeauna posibil. Astel, fiecarei muchii i se va atribui capacitatea $1$. Rulam algoritmul de flux maxim si retinem fluxul. Calculam, pentru fiecare muchie, maximul dintre distantele de la aceasta pana la nodul $1$ si pana la nodul $N$, apoi sortam descrescator muchiile, in functie de aceasta valoare.
In continuare, vom incerca sa gasim pozitia soldatului care ajunge ultimul la orasul atacat, parcurgand muchiile in ordinea sortarii: pentru o muchie $e$, vrem sa stabilim daca, pozitionand cel putin un soldat pe ea (crescand capacitatea la o valoare foarte mare), va creste sau nu fluxul. Daca nu va modifica valoarea fluxului, inseamna ca putem pune oricati soldati pe $e$, fara a influenta rezultatul final, deci muchia este inutila. Daca modifica valoarea fluxului, asta inseamna ca cel mai lenes soldat trebuie sa fie pozitionat pe $e$ si afisez valoarea maximului dintre distante pentru muchia respectiva.
In continuare, vom incerca sa gasim pozitia soldatului care ajunge ultimul in orasul atacat, parcurgand muchiile in ordinea sortarii: pentru o muchie $e$, vrem sa stabilim daca, pozitionand mai mult de un soldat pe ea (crescand capacitatea la o valoare foarte mare), va creste sau nu fluxul initial. Daca nu va modifica valoarea fluxului, inseamna ca putem pune oricati soldati pe $e$, fara a influenta rezultatul final, deci muchia este inutila. Daca modifica valoarea fluxului, asta inseamna ca cel mai lenes soldat trebuie sa fie pozitionat pe $e$ si afisez valoarea maximului dintre distante pentru muchia respectiva.
Pentru a avea o complexitate +teoretica+ de O(M*N^3), va trebui sa facem doua optimizari:
Pentru a avea o complexitate +teoretica+ de O(M*N^3) (in practica merge cu mult mai repede), va trebui sa facem doua optimizari:
# se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) +doar daca exista un drum nesaturat, ce contine si muchia $e$+
# se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) +doar daca exista un drum nesaturat, ce contine muchia $e$+
# pentru a verifica daca fluxul creste, nu se va relua tot algoritmul de flux maxim, ci se vor folosi informatiile anterior calcualte.
Desi nu ar fi trebuit sa ia decat $30$ de puncte, in solutia prezentata de Ionut Fechete, se putea inlocui Edmond-Karp cu algoritmul lui Dinic (vezi articolul lui Mugurel), obtinandu-se astfel punctaj maxim. Singurul care a facut acest lucru in concrus, a fost Bogdan Tataroiu.
