* '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#livada

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

* '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

Testul pe care pica Bellman-Ford:
* Muchiile 1 -> 2, 2 -> 3, 3 -> 4... N-1 - > N, toate de cost 1

* Muchiile 1 -> 3, 1 -> 5, 1 -> 7....1 ->N-1/N, toate de cost 10

* Muchiile 1 -> 3, 1 -> 5, 1 -> 7....1 ->N-1/N, prima de cost 10, a doua de cost 20, a treia de cost 30 etc.

Este nevoie de un shuffle foarte norocos al muchiilor din nodul 1 pentru ca algoritmul sa mearga bine.

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 minima a lui dp[i][h] cu h intre j si k.@

* pe linia i, @auxdp[j][k] = valoarea maxima 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

O problema aparent simpla.. Dar stati.. Nu putem sa precalculam raspunsurile pentru ca nu avem destula memorie. Nu putem sa raspundem offline la query-uri pentru ca avem nevoie de raspunsul de la ultimul query pentru a-l genera pe urmatorul. Ce este de facut ?

Avem foarte mult timp la dispozitie. Nu ne permitem ca pentru un query q sa pornim de la t=0 si sa urmam recurenta pana la t=q. Ce ne permitem in schimb este sa calculam la inceput valorile pana la pasul 10^7^ + 3 si sa retinem doar in anumite locuri rezultatul. Putem sa pornim cautarea atunci de la cel mai apropiat punct inainte de q. Vom retine evident rezultatul la puncte echidistante. Daca retinem rezultatul din <tex>{\sqrt{M}}</tex> in <tex>{\sqrt{M}}</tex> producem un echilibru intre timp si memorie. Complexitatea finala va fi <tex>O(M + Q*{\sqrt{M}})</tex> ca timp si <tex>O({\sqrt{M}})</tex> ca memorie. Limita de memorie ne permite si mai mult. Cu cat gap-ul dintre punctele precalculate este mai mic, cu atat solutia va fi mai rapida.

Avem foarte mult timp la dispozitie. Nu ne permitem ca pentru un query q sa pornim de la t=0 si sa urmam recurenta pana la t=q. Ce ne permitem in schimb este sa calculam la inceput valorile pana la pasul 10^7^ + 3 si sa retinem doar in anumite locuri rezultatul. Putem sa pornim cautarea atunci de la cel mai apropiat punct inainte de q. Vom precalcula rezultatul la puncte echidistante. Daca retinem rezultatul din <tex>{\sqrt{M}}</tex> in <tex>{\sqrt{M}}</tex> producem un echilibru intre timp si memorie. Complexitatea finala va fi <tex>O(M + Q*{\sqrt{M}})</tex> ca timp si <tex>O({\sqrt{M}})</tex> ca memorie. Limita de memorie ne permite si mai mult. Cu cat gap-ul dintre punctele precalculate este mai mic, cu atat solutia va fi mai rapida.

==include(page="onis-2015/solutii-runda-1/semipal")==