* 'Por Costel şi Comisia de Cenzură':onis-2015/solutii-runda-1#cenzura
* 'Por Costel şi Cifrul':onis-2015/solutii-runda-1#cifrul
* 'Por Costel şi Invazia Extraterestră':onis-2015/solutii-runda-1#invazia

* 'Por Costel şi Livada':onis-2015/solutii-runda-1#livada2

* 'Por Costel şi Livada':onis-2015/solutii-runda-1#livada

* 'Por Costel şi Meciul':onis-2015/solutii-runda-1#meciul
* 'Por Costel şi Perechile':onis-2015/solutii-runda-1#perechile
* 'Por Costel şi Pinball':onis-2015/solutii-runda-1#pinball

Vrem sa coboram complexitatea la <tex>O(N*M^2^)</tex>. Valorile lui s si mv sunt usor de obtinut in <tex>O(M^2^)</tex> pe linie parcurgand subsecventele de coloane in modul corespunzator. Problema este cum actualizam ? Vom utiliza o dinamica auxiliara independenta de linii (adica una care se refera doar la o singura linie la un moment dat).

* pe linia i, @auxdp[j][k] = valoarea maxima a lui dp[i][h] cu h intre j si k.@

* pe linia i, @auxdp[j][k] = valoarea minima a lui dp[i][h] cu h intre j si k.@

Definitia ne ajuta mai putin sa intelegem functionalitatea acestei dinamici. Ce facem cu ea este ca atunci cand am calculat s(i,j,k) + mv(i-1,j,k) pentru o subsecventa (j,k) in loc sa facem un _for_ de la j la k, incarcam valoarea in @auxdp[j][k]@. Dupa ce am parcurs toate subsecventele de coloane, le parcurgem a doua oara, de data aceasta in ordinea inversa a lungimii si actualizam in felul urmator:
* auxdp[j+1][k] = max (auxdp[j+1][k], auxdp[j][k]) cu j < k

Daca un baiat are stangacia x, atunci numarul de fete cu care poate dansa este [n/x].
Deci trebuie sa calculam [n/1] + [n/2] + [n/3] + ... + [n/n].

Ne permitem sa calculam suma pana la <tex>{\sqrt{N}}</tex>. De acolo putem constata ca exista <tex>{\sqrt{N}}</tex> intervale de numere, pe un interval toate numerele i avand acelasi rezultat al expresiei [n/i]. Putem sa aflam primul si ultimul numar din intervalul care il are ca rezulatat al expresiei pe rez: acestea sunt n/(rez+1) + 1 si n/rez.

Ne permitem sa calculam suma pana la <tex>{\sqrt{N}}</tex>. De acolo putem constata ca exista <tex>{\sqrt{N}}</tex> intervale de numere, pe un interval toate numerele i avand acelasi rezultat al expresiei [n/i]. Putem sa aflam primul si ultimul numar din intervalul care il are ca rezulatat al expresiei pe rez: acestea sunt n/(rez-1) + 1 si n/rez.

O solutie mult mai simpla si mai rapida este sa ne dam seama ca intr-o pereche (a,b) cu a*b &le; N cel putin unul dintre a si b este &le; <tex>{\sqrt{N}}</tex> Putem sa calculam cu formula de mai sus sol = nr. de perechi in care stangacia fetelor este &le; <tex>{\sqrt{N}}</tex>. Atunci tot acesta va fi numarul de perechi in care stangacia baietilor este &le; <tex>{\sqrt{N}}</tex>. Atunci raspunsul final = 2*sol - @cate perechi exista in care atat stangacia fetelor cat si a baietilor este@ &le; <tex>{\sqrt{N}}</tex>. Acesta din urma este chiar [<tex>{\sqrt{N}}</tex>]^2^

Complexitate <tex>O(N + M)</tex>

*Demonstratie*: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S+1.

*Demonstratie*: Vom considera sirul divizat in 'secvente de monotonie'. Doua secvente de monotonie consecutive sunt legate printr-un varf (care apartine amandurora). Fie V = numarul de varfuri si S = numarul de secvente de monotonie. Are loc relatia V = S-1.

* Consideram toate solutiile pentru care avem cel mult un element pe fiecare secventa de monotonie: atunci evident sol &le; S < V.
* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu doua elemente. Daca alegem o secventa de monotonie pe care alegem doua elemente, pe restul secventelor este imposibil sa alegem doua si vom alege cel mult 1, atunci sol &le; S+1 = V