h3. (clasele 11-12, problema usoara)

Foarte multi concurenti au incercat sa rezolve aceasta problema folosind algoritmul Dijkstra cu heap-uri sau cu arbori de intervale. Aceasta solutie ar fi obtinut de la $70$ pana la $100$ de puncte (in cazul in care se optimiza algoritmul). O alta metoda de a obtine $100$ de puncte ar fi fost folosirea algoritmul Bellman Ford cu coada (vezi OJI 2004, problema "Lanterna":http://infoarena.ro/task/lanterna).

Foarte multi concurenti au incercat sa rezolve aceasta problema folosind algoritmul Dijkstra cu heap-uri sau cu arbori de intervale. Aceasta solutie ar fi obtinut de la $70$ pana la $100$ de puncte (in cazul in care se optimiza algoritmul). O alta metoda de a obtine $100$ de puncte ar fi fost folosirea algoritmul Bellman Ford cu coada (vezi OJI 2004, problema "Lanterna":http://infoarena.ro/problema/lanterna).

Solutia oficiala (care este de fapt si cea mai simpla si cea mai usor de implementat) are complexitate $O(N+M)$ ca timp si $O(N)$ ca memorie. Ea poate fi dedusa din modul de functionare a algoritmilor Dijkstra sau Bellman Ford. Asadar, conditile suficiente si necesare ca distantele minime date sa fie corecte sunt:

h3. (clasele 11-12, problema grea)

Problema a fost gandita sa rasplateasca pe "fanii infoarena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/task/secventa, "Secventa 2":http://infoarena.ro/task/secv2, "Secventa 3":http://infoarena.ro/task/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice 2N*2M, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Problema a fost gandita sa rasplateasca pe "fanii infoarena" si anume pe aceea care au rezolvat corect problemele "Secventa 1":http://infoarena.ro/problema/secventa, "Secventa 2":http://infoarena.ro/problema/secv2, "Secventa 3":http://infoarena.ro/problema/secv3. Pentru a trata circularitatea matricii o vom extinde intr-o matrice 2N*2M, lipind matrii initiale o copie la dreapta, sub ea, si la dreapta-jos.

Rezolvarea acum se va baza pe cautarea binara a balansului maxim (idee folosita si la rezolvarea problemei "Secventa 3":http://infoarena.ro/task/secv3). Fie acesta {$X$}, trebuie sa verificam daca exista o submatrice cu balans cel putin {$X$}, adica:

Rezolvarea acum se va baza pe cautarea binara a balansului maxim (idee folosita si la rezolvarea problemei "Secventa 3":http://infoarena.ro/problema/secv3). Fie acesta {$X$}, trebuie sa verificam daca exista o submatrice cu balans cel putin {$X$}, adica:

* $Suma / Numar ≥ X$
* $Suma ≥ X*Numar$

Folosind cele scrise mai sus, putem observa ca, daca fiecare element nr din matricea intiala este inlocuit cu {$nr-X$}, atunci problema se reduce la a determina o submatrice din matricea modificata in care suma elementelor este {$≥ 0$}. Aceasta problema se poate rezolva determinand submatricea de suma maxima din matricea modificata, verificand apoi daca este {$≥ 0$}.

Asadar, problema s-a redus la a determina o submatrice de cel putin $R$ linii si $C$ coloane de suma maxima dintr-o matrice. Intai vom fixa $2$ linii la distanta cel putin $R$ si cel mult {$N$}, si vom calcula sumele pe coloane intre cele doua linii (acest lucru se poate face in $O(M)$ precalculand anumite sume la inceput). Pe vectorul de sume pe coloane obtinut va trebui sa rezolvam acum problema "secventei de suma maxima de lungime intre {$C$} si {$M$}" (necesara si la rezolvarea problemei "Secventa 3":http://infoarena.ro/task/secv3). Fie $A$ vectorul pe care vrem sa rezolvam acesta problema, si {$S{~i~} = A{~1~}+A{~2~}+...+A{~i~}$}. Pentru fiecare $i$ va trebui sa gasim un $j$ astfel incat:

Asadar, problema s-a redus la a determina o submatrice de cel putin $R$ linii si $C$ coloane de suma maxima dintr-o matrice. Intai vom fixa $2$ linii la distanta cel putin $R$ si cel mult {$N$}, si vom calcula sumele pe coloane intre cele doua linii (acest lucru se poate face in $O(M)$ precalculand anumite sume la inceput). Pe vectorul de sume pe coloane obtinut va trebui sa rezolvam acum problema "secventei de suma maxima de lungime intre {$C$} si {$M$}" (necesara si la rezolvarea problemei "Secventa 3":http://infoarena.ro/problema/secv3). Fie $A$ vectorul pe care vrem sa rezolvam acesta problema, si {$S{~i~} = A{~1~}+A{~2~}+...+A{~i~}$}. Pentru fiecare $i$ va trebui sa gasim un $j$ astfel incat:

* $S[i] - S[j]$ = maxim
* $i-M ≤ j ≤ i-C$