Problema se rezolva prin programare dinamica. Vom considera $2$ matrici:
* $A{~i~}~,~ {~j~}$ = $1$ daca intervalul de jetoane dintre pozitiile $i$ si $j$ poate fi eliminat, sau $0$, altfel.

* $B{~i~}~,~ {~j~}~,~ {~k~}$ = $1$ daca undeva intre pozitiile $i$ si $j$ se poate plasa al $k$-lea cuvant si sa poate elimina +tot+ intervalul, sau $0$, altfel.

* $B{~i~}~,~ {~j~}~,~ {~k~}$ = $1$ daca intre pozitiile $i$ si $j$ se poate plasa al $k$-lea cuvant si se poate elimina +tot+ intervalul, sau $0$, altfel.

Astel $B{~i~}~,~ {~j~} {~k~}$ = $1$ daca si numai daca exista un $p$ ∈ [$i$, $j$], astfel incat:

Astfel $B{~i~}~,~ {~j~} {~k~}$ = $1$ daca si numai daca exista un $p$ ∈ [$i$, $j$], astfel incat:

# $Cuv{~k~}~,~ {~l~} = Sir{~p+l~}$, ∀ $1$ ≤ $l$ ≤ $Lung{~k~}$
# $A{~i~}~,~ {~p-1~} = A ~(i+Lung{~k~})~ ~,~ ~j~ = 1$

h2. 'Tero':problema/tero (problema grea)

Dupa cum multi si-au dat seama, problema este asemanatoare cu cea a lui Fechete, "Trafic":http://infoarena.ro/problema/trafic.

Dupa cum multi si-au dat seama, problema este asemanatoare cu cea a lui Dan Ionut Fechete, "Trafic":http://infoarena.ro/problema/trafic.

Fiind niste limite de timp foarte mari, "cautare binara + fluxul":http://campion.edu.ro/problems.php?mode=view_solution&problem_id=279&group_number=3&year=2005 nu intra in timp.

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.

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 celui mai lenes soldat, parcurgand muchiile in ordinea sortarii, astfel: 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.

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.

Pentru a avea o complexitate +teoretica+ de O(M*N^3), va trebui sa facem doua optimizari:

# se va reface reteaua reziduala L0 (vezi articolul lui Mugurel) +doar daca distanta 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 si 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.