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

Relatia de recurenta:
* @Daca numarul v[i] este par:@

** @dp[i][0] = 2 * dp[i-1][1]@

** @dp[i][0] = 2 * dp[i-1][0]@

** @dp[i][1] = 2 * dp[i-1][1]@
* @Daca numarul v[i] este impar:@
** @dp[i][0] = dp[i-1][0] + dp[i-1][1]@

Stim ca aloritmul va lua cel putin doua iteratii pentru ca se garanteaza ca exista cel putin o muchie care iese din nodul 1. Pentru ca algoritmul lui Por Costel sa se termine in doua iteratii, trebuie ca doar la prima iteratie sa se produca relaxari ale muchiilor (modificari ale vectorului d). Cand se intra in iteratia a doua trebuie ca in vectorul d sa existe deja valorile drumurilor minime pentru a nu se produce nicio modificare, variabila _ok_ sa ramana cu valoarea 1 si sa nu se mai intre in while a treia oara.

Pentru a rezolva problema sunt necesare niste cunostiinte generale despre problema drumurilor minime intr-un graf, de exemplu, faptul ca reuniunea drumurilor minime din nodul $x$ catre toate celelalte noduri formeaza un arbore (arborele partial al drumurilor minime din $x$). Observam ca daca muchiile din acest arbore sunt parcurse in ordinea unei parcurgeri din nodul $x$ (DFS sau BFS sau orice fel de parcurgere), drumurile minime se vor propaga complet. Deci solutia este o astfel de ordonare a @N-1@ @muchii care formeaza un arbore partial de drumuri minime din nodul 1 iar restul de @M-N+1@ muchii pot fi interclasate cu acestea in orice fel.

Pentru a rezolva problema sunt necesare niste cunostiinte generale despre problema drumurilor minime intr-un graf, de exemplu, faptul ca reuniunea drumurilor minime din nodul $x$ catre toate celelalte noduri formeaza un arbore (arborele partial al drumurilor minime din $x$). Observam ca daca muchiile din acest arbore sunt parcurse in ordinea unei parcurgeri din nodul $x$ (DFS sau BFS sau orice fel de parcurgere), drumurile minime se vor propaga complet. Deci solutia va reprezenta o astfel de ordonare a @N-1@ muchii care formeaza un arbore partial de drumuri minime din nodul 1 iar restul de @M-N+1@ muchii pot fi interclasate cu acestea in orice fel.

Pentru a construi un arbore partial de drumuri minime din nodul 1, trebuie sa aplicam un algoritm de drum minim. O solutie este chiar Bellman-Ford dar acesta are complexitate O(N*M) chiar si daca il codezi mai bine ca Por Costel. Pentru ca muchiile din graf au cost pozitiv, drumurile minime se pot calcula folosind '$algoritmul lui Dijkstra$':http://www.infoarena.ro/problema/dijkstra

Pentru a construi un arbore partial de drumuri minime din nodul 1, trebuie sa aplicam un algoritm de drum minim. O solutie este chiar Bellman-Ford dar acesta are complexitate <tex> O(N*M) </tex> chiar si daca il codezi mai bine ca Por Costel. Pentru ca muchiile din graf au cost pozitiv, drumurile minime se pot calcula folosind '$algoritmul lui Dijkstra$':http://www.infoarena.ro/problema/dijkstra

Complexitatea: <tex>O(M*logN)</tex>
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.
==include(page="onis-2015/solutii-runda-1/bujor")==
Constatarea cheie aici este ca daca inmultim matricele $B$ si $P$ obtinem matricea $I$ cu semnificatia:  @I[i][j] = total expected winnings pentru Bujor in casino-ul i, in ziua j@.

Observam ca matricele I care satisfac cerinta finala sunt matricele permutare, printe care se numara si matricea identitate $I$~n~. Deci matricea P poate fi inversa matricei B. Matricea B este garantat inversabila deoarece se garanteaza ca exista solutie la problema (Ecuatia matriceala @B*P = I@ cu _det(I)_ nenul are solutie doar daca _det(B)_ este si el nenul)

Observam ca matricele $I$ care satisfac cerinta finala sunt matricele permutare, printe care se numara si matricea identitate $I$~n~. Deci matricea P poate fi inversa matricei B. Matricea B este garantat inversabila deoarece se garanteaza ca exista solutie la problema (Ecuatia matriceala @B*P = I@ cu _det(I)_ nenul are solutie doar daca _det(B)_ este si el nenul)

Inversa matricei se poate calcula in <tex>O(N^3)</tex> cu o variatie a 'algoritmului lui Gauss':http://www.infoarena.ro/problema/gauss care se cheama eliminare Gauss-Jordan. Prin inmultiri de linii cu constante, si scadere de linii din alte linii, putem aduce matricea B la matricea $I$~n~. Atunci operatiile pe care le-am efectuat sunt echivalente cu inmultirea cu matricea B^-1^. Daca retinem aceste operatii si le aplicam pe matricea $I$~n~, vom obtine matricea B^-1^. Mai multe explicatii/informatii se gasesc si 'aici':http://en.wikipedia.org/wiki/Gaussian_elimination

Inversa matricei se poate calcula in <tex>O(N^3)</tex> cu o variatie a 'algoritmului lui Gauss':http://www.infoarena.ro/problema/gauss care se cheama eliminare Gauss-Jordan. Prin inmultiri de linii cu constante, si scadere de linii din alte linii, putem aduce matricea B la matricea $I$~n~. Atunci operatiile pe care le-am efectuat sunt echivalente cu inmultirea cu matricea B^-1^. Daca retinem aceste operatii si le aplicam pe matricea $I$~n~, vom obtine matricea    B^-1^. Mai multe explicatii/informatii se gasesc si 'aici':http://en.wikipedia.org/wiki/Gaussian_elimination

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

*Subproblema 1*

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat 'Aho-Corasick':http://www.infoarena.ro/problema/ahocorasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic $mathces$, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul $matches$ al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al unui prefixului i al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului $matces$ al nodului curent in vectorii $matches$ ai nodurilor in care ajungem urmarind pointerul de nepotrivire _fail_. Putem scoate pozitiile de potrivire ale cuvintelor din vectorii _matches_ ale nodurilor terminale.

Aceasta problema admite mai multe solutii, insa cea de complexitate optima se foloseste de un automat 'Aho-Corasick':http://www.infoarena.ro/problema/ahocorasick. Va rugam sa-l studiati inainte de a citi mai departe. Vom numi nod terminal un nod din Aho-Corasick in care se termina un cuvant din dictionar. Fiecare nod din automat va avea un vector dinamic $mathces$, o lista cu indici ai prefixelor din text pentru care cuvantul determinat de acest nod (mai precis de drumul de la radacina la acest nod) este sufix. Atunci cand 'trecem textul prin automat' incarcam fiecare indice i din text (care reprezinta prefixul care se termina la pozitia i) in vectorul $matches$ al nodului la care am ajuns la momentul respectiv. Acesta va fi cel mai lung prefix al unui cuvant din dictionar care este sufix al prefixului i al sirului. Pentru a afla toate prefixele din dictionar care sunt sufixe ale acestui prefix i, este suficient sa copiem continutul vectorului $matces$ al nodului curent in vectorii $matches$ ai nodurilor in care ajungem urmarind pointerul de nepotrivire _fail_. Apoi, putem scoate pozitiile de potrivire ale cuvintelor din vectorii _matches_ ale nodurilor terminale.

Atentie ! Aici se poate cadea intr-o capcana. Problema garanteaza ca numarul de aparitii ale cuvintelor din dictionar in text nu depaseste 10^4^, dar problema nu garanteaza pentru numarul de aparitii ale prefixelor cuvintelor din dictionar.

Problema aceasta se trateaza prin programare dinamica. Este clar ca putem inlatura intervalele care contin alte intervale. Dinamica de mai jos functioneaza si daca nu facem aceasta reducere, dar o sa consideram ca o facem pentru ca simplifica explicatia:

Intervalele sunt acum lipsite de parantezari deci o sortare dupa capatul stanga reprezinta si o sortare dupa capatul dreapta. Indexam intervalele dupa aceasta ordine. Al i-lea interval este cel cu al i-lea capat stanga. Deoarece alegand o pozitie i din text acoperim o secventa continua de astfel de intervale, putem construi dinamica:

Intervalele sunt acum lipsite de parantezari deci o sortare dupa capatul stanga reprezinta si o sortare dupa capatul dreapta. Indexam intervalele dupa aceasta ordine. Al i-lea interval este cel cu al i-lea capat stanga. Deoarece alegand o pozitie k de pe axa Ox acoperim o secventa continua de astfel de intervale, putem construi dinamica:

* @dp[i] = costul minim de a acoperi primele i intervale.@

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale la care suntem la pozitia i. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa actualizam @dp[k] = min (dp[k], dp[l-1] + v[i])@ pentru oricare k cu l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale. Presupunem ca suntem la pozitia i si stim configuratia de intervale care trece prin aceasta pozitie. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa actualizam @dp[k] = min (dp[k], dp[l-1] + v[i])@ pentru oricare k cu l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

== code(cpp) |
int get_answer (vector<pair<int,int> > intervals)

Problema se poate rezolva mentinand in fiecare nod al unui arbore de intervale o structura de date auxiliara care sa poata sa raspunda rapid la inserari, stergeri si query-uri de minim (de exemplu, heap). Insa, cum operatiile de inserare si stergere la problema aceasta sunt parantezate corect, este indeajuns o stiva.

Cand primim o inserare, descompunem intervalul primit in cele $logN$ noduri corespunzatoare din arborele de intervale, iar in varful stivei din fieacre din aceste noduri incarcam min(inaltimea noii nave, varful precedent al stivei). La stergere, luam intervalul asociat ultimei inserari (care il vom memora probabil tot cu ajutorul unei stive) si, din nou, il descompunem in cele $logN$ noduri asociate, pe stivele carora apelam $pop$()(stergem varful).

Cand primim o inserare, descompunem intervalul primit in cele $logN$ noduri corespunzatoare din arborele de intervale, iar in varful stivei din fiecare din aceste noduri incarcam min(inaltimea noii nave, varful precedent al stivei). La stergere, luam intervalul asociat ultimei inserari (care il vom memora probabil tot cu ajutorul unei stive) si, din nou, il descompunem in cele $logN$ noduri asociate, pe stivele carora apelam $pop$()(stergem varful).

De notat este ca problema nu necesita lazy-update, intrucat query-urile sunt punctiforme (nu sunt pe interval). Un query va parcurge pe arborele de intervale un drum de la radacina la o frunza. Daca in fiecare dintre nodurile de pe drum, ne uitam la ce se afla in varful stivei, raspunsul pentru query va fi minimul dintre aceste valori.

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.@
 
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, parcurgem din nou subsecventele de coloane, de data aceasta in ordinea inversa a lungimii si actualizam in felul urmator:

* 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
* auxdp[j][k-1] = max (auxdp[j][k-1], auxdp[j][k]) cu j < k

*Solutia 1*

La fiecare moment, mentinem liste cu noduri, o lista reprezentand o componenta conexa din graf la acel moment (initial avem N liste a cate un singur element fiecare). In plus, pentru oricare nod retinem carei liste ii apartine si, in cadrul acelei componente conexe, in ce 'echipa' se afla. Daca primim un query intre doua noduri care apartin aceleiasi componente conexe, acesta este usor de tratat(NO daca sunt de aceeasi parte, YES daca sunt de parti diferite). Interesant este ce facem daca nodurile sunt din doua componente conexe diferite. Trebuie sa le punem intr-o singura lista cu informatii actualizate. Observam totusi ca nu este nevoie sa ne atingem decat de nodurile uneia din liste. Nodurile dintr-o lista le vom introduce in cealalta lista (lista lor originala o vom elimina) si le vom plasa in 'echipe' relativ la nodurile din aceasta lista. Daca alegem intotdeauna sa mutam nodurile din lista mai mica in lista mai mare, complexitatea va fi <tex>O(M + N*logN)</tex>. Va lasam pe voi sa va ganditi de ce. (indiciu: nodurile vor apartine in final unei singure liste, ganditi-va de cate ori poate fi mutat un nod pana sa faca parte din lista finala).

La fiecare moment, mentinem liste cu noduri, o lista reprezentand o componenta conexa din graf la acel moment (initial avem N liste a cate un singur element fiecare). In plus, pentru oricare nod retinem carei liste ii apartine si, in cadrul acelei componente conexe, in ce 'echipa' se afla. Daca primim un query intre doua noduri care apartin aceleiasi componente conexe, acesta este usor de tratat(NO daca sunt de aceeasi parte, YES daca sunt de parti diferite). Interesant este ce facem daca nodurile sunt din doua componente conexe diferite. Trebuie sa le punem intr-o singura lista cu informatii actualizate. Observam totusi ca nu este nevoie sa ne atingem decat de nodurile uneia din liste. Nodurile dintr-o lista le vom introduce in cealalta lista (lista lor originala o vom elimina) si le vom plasa in 'echipe' relativ la nodurile din aceasta lista. Daca alegem intotdeauna sa mutam nodurile din lista mai mica in lista mai mare, complexitatea va fi <tex>O(M + N*logN)</tex>. Va lasam pe voi sa va ganditi de ce. (indiciu: nodurile vor apartine in final unei singure liste iar din momentul acela nu vor mai exista mutari, ganditi-va de cate ori poate fi mutat un nod pana sa faca parte din lista finala).

*Solutia 2*

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

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^

Complexitatea este <tex>O({\sqrt{N}})</tex>
==include(page="onis-2015/solutii-runda-1/pinball")==

Dandu-se un sir de numere, care este cel mai lung subsir alternant ? este intrebarea pusa de aceasta problema.

Dandu-se un sir de numere, care este lungimea celui mai lung subsir alternant ? este intrebarea pusa de aceasta problema.

Dificultatea acestei probleme consta in a face urmatoarea constatare:

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

* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu trei elemente: Nu exista

* Consideram toate solutiile pentru care avem cel putin o secventa de monotonie cu trei elemente: Nu exista.

Atunci sol ≤ V oricare ar fi sol - lungimea unui sir alternant. Atunci V este valoarea maxima a lungimii unui subsir alternant.

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^ 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 o balansare 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")==

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

Sa distilam ce inseamna un semiplaindrom. Ca un cuvant sa fie semipalindrom este necesar si suficient ca ultima litera sa fie egala cu prima. Atunci numarul de semipalindroame de lungime N formate din 'a' si 'b' este 2^N-1^ - deci K se va incadra in tipul @long long@. Configuratia binara a lui K va dicta primele N-1 litere din sir (1 inseamna 'b' si 0 inseamna 'a') iar ultima litera este unic determinata de prima. Vedeti ? Nu-i asa greu la Petrozaporksk.