h2. 'Imagine':problema/imagine
Observam ca fiecare din operatiile {$S$} {$D$} {$O$} {$V$} nu face decat sa permute intre ele cele $4$ cadrane. De exemplu initial cadranele se afiseaza in ordinea {$1,2,3,4$} iar dupa o operatie {$O$} vor trebui afisate {$3,4,1,2$}, apoi dupa aplicarea unei operatii $V$ va trebui afisat {$4,3,2,1$}. Pentru operatiile $N$ va trebui sa retinem doar paritatea si in cazul in care numarul acestor operatii este impar va trebui sa afisam $n$ in loc de $a$ si invers. De aceea nu trebuie decat sa retinem in ce ordine vom prezenta cadranele si daca acestea vor fi sau nu negate.
Observam ca fiecare din operatiile {$S$} {$D$} {$O$} {$V$} nu face decat sa permute intre ele cele $4$ cadrane. De exemplu initial cadranele se afiseaza in ordinea {$1,2,3,4$} iar dupa o operatie {$O$} vor trebui afisate {$3,4,1,2$}, apoi dupa aplicarea unei operatii $V$ va trebui afisat {$4,3,2,1$}. Pentru operatiile $I$ va trebui sa retinem doar paritatea si in cazul in care numarul acestor operatii este impar va trebui sa afisam $n$ in loc de $a$ si invers. De aceea nu trebuie decat sa retinem in ce ordine vom prezenta cadranele si daca acestea vor fi sau nu negate.
Problema care se ridica este lipsa memoriei. Vom reprezenta imagina ca un arbore in care fiecare nod fie este frunza fie are $4$ fii(cate unul pentru fiecare cadran). O parcurgere a arborelui in care fii oricarui nod sunt parcursi in ordinea permutarii noastre va fi exact codificarea cautata. Obervam ca nu putem avea mai mult de $N/5$ nodui interne deci maxim {$2.000.000$}. Pentru fiecare nod vom retine primul fiul si fratele nodului curent. Din felul in care vom construi arborele (cu ajutorul unei stive) se vede ca primul fiu al unui nod in cazul in care exista va fi exact {$nodul curent + 1$} de aceea nu va mai fi necesara si retinerea fiului. In plus in fiecare nod vom mai retine 8 biti grupati cate 2 pentru a retine pentru fiecare din cei $4$ fii daca este sau nu o frunza si in cazul in care este o frunza retinem si culoarea ei. In total se poate folosi cu usurinta sub $16M$ memorie.
Problema care se ridica este lipsa memoriei. Vom reprezenta imaginea ca un arbore in care fiecare nod fie este frunza fie are $4$ fii(cate unul pentru fiecare cadran). O parcurgere a arborelui in care fii oricarui nod sunt parcursi in ordinea permutarii noastre va fi exact codificarea cautata. Observam ca nu putem avea mai mult de $N/5$ noduri interne deci maxim {$2.000.000$}. Pentru fiecare nod vom retine primul fiul si fratele nodului curent. Din felul in care vom construi arborele (cu ajutorul unei stive) se vede ca primul fiu al unui nod in cazul in care exista va fi exact {$nodul curent + 1$} de aceea nu va mai fi necesara si retinerea fiului. In plus in fiecare nod vom mai retine 8 biti grupati cate 2 pentru a retine pentru fiecare din cei $4$ fii daca este sau nu o frunza si in cazul in care este o frunza retinem si culoarea ei. In total se poate folosi cu usurinta sub $16M$ memorie.
h2. 'Strigat':problema/strigat
Vom construi un "automat finit":Automate-finite-si-KMP ce va contine cuvintele din intrare. Fiecarei stari din automat ii vom asocia o valoare egala cu suma gradelor de spaima ale cuvintelor acceptate de acea stare. Pentru a determina sirul cu grad maxim de spaima vom construi matricea $A[i][j]$ cu semnificatia care este gradul de spaima maxim pentru un sir de lungime $i$, aflandu-ne la sfarsit in starea $j$ a automatului. Aflandu-ne pe linia $i$ a matricei vom folosi matricea de tranzitie a automatului $δ$ pentru a calcula valorile de pe linia $i + 1$.
$A[i + 1][ δ{~j, c~} ] = max( A[i + 1][ δ{~j, c~} ], A[i][j] + ValoareStare[ δ{~j, c~} ] )$, $c ∈ Σ$
Constructia automatului are complexitatea $O(L * |Σ|)$, unde $L$ reprezinta suma lungimilor cuvintelor de la intrare si $Σ$ reprezinta alfabetul.
Calcularea matricei are complexitatea $O(N * L * |Σ|)$.
h2. 'Flux':problema/flux
Vom forma un sistem de ecuatii in care necunoscutele {$X{~i~}$} vor fi suma fluxurilor de pe drumul de la $0$ la nodul {$i$} (care se garanteaza ca este aceeasi indiferent de drum). Fluxul trimis de la $i$ la $j$ va fi exact {$n{~i,j~}*(X{~j~}-X{~i~})$} unde n{~i,j~} este numarul de muchii dintre $i$ si {$j$}. Vom pune conditiile de conservare a fluxului pentru fiecare nod {$i$}: suma fluxurilor care intra sa fie egala cu suma fluxurilor care ies. Pentru nodul $1$ nu este necesar sa scriem ecuatia deoarece se stie {$X{~1~}=0$}, iar pentru nodul $N$ vom pune ecuatia suma fluxurilor care intra in el sa fie $1$. Sistemul de {$N-1$} ecuatii cu {$N-1$} necunoscute se rezolva folosind Gauss.
