h2. Matrix
(problema grea clasa a 9-a, problema medie clasa a 10-a)
Primul pas al algoritmului este calcularea numarului de aparitii ale fiecarei litere in matricea de N*N. Prima idee care ne vine in minte este ca pentru toate submatricile posibile sa calculam numarul de aparitii ale fiecarei litere si sa comparam cu valorile care trebuie obtinute. Acest algoritm are complexitatea O(M^2*(N+S)), unde S este dimensiunea alfabetului. Aceasta abordare obtine 50 de puncte. Vom verifica pentru toate cele (M-N)^2 matrici posibile daca sunt sau nu permutari ale matricii-template. Apoi, pentru fiecare litera a alfabetului, efectuam urmatoarea preprocesare pentru a putea calcula in O(1) numarul de aparitii ale literei din orice submatrice: T[i][j] = numarul de aparitii pe pozitii (x, y) cu 1 <= x <= i si 1 <= y <= j.
Relatia de recurenta este T[i][j] = T[i-1][j]+T[i][j-1]-T[i-1][j-1], la care se adauga 1 daca si numai daca pe pozitia (i, j) se afla litera pe care o cautam. In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in (i-N+1, j-N+1) si (i, j) este T[i][j]-T[i-N][j]-T[i][j-N]+T[i-N][j-N]. Aceasta solutie are complexitatea O(M^2*S). Daca se foloseste O(M^2*S) memorie se obtin 70-80 de puncte, iar pentru punctaj maxim este necesara reducerea la O(M^2). Acest lucru poate fi realizat folosind doua matrici, una in care tinem minte daca pentru o anumita pozitie s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit, si una in care se efectueaza preprocesarea pentru litera curenta. O alta optimizare, mult mai nesimnificativa, si care nu este necesara pentru 100 de puncte, este renuntarea la verificarea pentru ultima litera, deoarece daca primele 25 de litere s-au potrivit, iar numarul de litere este constant, e clar ca si cea de-a 26-a litera se va
potrivi.
Primul pas al algoritmului este calcularea numarului de aparitii ale fiecarei litere in matricea de $N*N$. Prima idee care ne vine in minte este ca pentru toate submatricile posibile sa calculam numarul de aparitii ale fiecarei litere si sa comparam cu valorile care trebuie obtinute. Acest algoritm are complexitatea $O(M^2*(N+S)^)$, unde $S$ este dimensiunea alfabetului. Aceasta abordare obtine $50$ de puncte.
Vom verifica pentru toate cele {@(M-N)@}$^2^$ matrici posibile daca sunt sau nu permutari ale matricii-template. Apoi, pentru fiecare litera a alfabetului, efectuam urmatoarea preprocesare pentru a putea calcula in $O(1)$ numarul de aparitii ale literei din orice submatrice: $T{~i,j~}$ = numarul de aparitii pe pozitii $(x, y)$ cu $1 ≤ x ≤ i$ si $1 ≤ y ≤ j$.
Relatia de recurenta este $T{~i,j~} = T{~i-1,j~}+T{~i,j-1~}-T{~i-1,j-1~}$, la care se adauga $1$ daca si numai daca pe pozitia $(i, j)$ se afla litera pe care o cautam. In aceste conditii, numarul de aparitii ale literei curente in submatricea cu colturile in $(i-N+1, j-N+1)$ si $(i, j)$ este $T{~i,j~}-T{~i-N,j~}-T{~i,j-N~}+T{~i-N,j-N~}$. Aceasta solutie are complexitatea $O(M^2*S^)$. Daca se foloseste $O(M^2*S^)$ memorie se obtin $70-80$ de puncte, iar pentru punctaj maxim este necesara reducerea la $O(M^2^)$. Acest lucru poate fi realizat folosind doua matrici, una in care tinem minte daca pentru o anumita pozitie s-a gasit vreo litera pentru care numarul de aparitii nu coincide cu cel dorit, si una in care se efectueaza preprocesarea pentru litera curenta. O alta optimizare, mult mai nesimnificativa, si care nu este necesara pentru $100$ de puncte, este renuntarea la verificarea pentru ultima litera, deoarece daca primele $25$ de litere s-au potrivit, iar numarul de litere este constant, e clar ca si cea de-a $26$-a litera se va potrivi.
h2. Lista lui Andrei
(problema usoara clasa a 10-a)
Problema se rezolva folosind programare dinamica. Putem tine o matrice $V{~1..N~}{~1..26~}$ unde $V{~i,j~}$ reprezinta numarul de siruri de lungime $i$ ce contin ultima litera $j$. Incepem completarea matricii in ordine crescatoare a lungimii sirurilor, iar $V{~i,j~}$ se obtine prin insumarea valorilor V{~i-1,k~}, pentru orice $k$ a.i perechea $(k, j)$ sau $(j, k)$ sa nu se regaseasca in lista. Acest rationament conduce la un algoritm in $O(N * Σ^2^)$, unde $Σ$ reprezinta marimea alfabetului (in cazul nostru $26$).
Calcul
Problema se rezolva folosind programare dinamica. Putem tine o matrice $V{~1..N~}{~1..26~}$ unde $V{~i,j~}$ reprezinta numarul de siruri de lungime $i$ ce contin ultima litera $j$. Incepem completarea matricii in ordine crescatoare a lungimii sirurilor, iar $V{~i,j~}$ se obtine prin insumarea valorilor $V{~i-1,k~}$, pentru orice $k$ a.i perechea $(k, j)$ sau $(j, k)$ sa nu se regaseasca in lista. Acest rationament conduce la un algoritm in $O(N * Σ^2^)$, unde $Σ$ reprezinta marimea alfabetului (in cazul nostru $26$).
h2. Calcul
(problema grea clasa a 10-a, problema medie clasele 11-12)
Deoarece se cer doar ultimele C cifre se va lucra modulo 10^C. Asadar, la primul pas se va calcula A modulo 10^C, adica ne intereseaza doar ultimele C cifre din A.
O prima solutie pentru a calcula A^1 + A^2 + ... + A^B este de calcula A^i in O(lg i) pentru fiecare i folosind algoritmul clasic de ridicare la o putere in numar logaritmic de pasi (Cormen, capitolul 33). Aceasta solutie ar fi adus doar 20p.
Suma prezentata este o progresie geometrica clasica, si se poate calcula folosind formula (A^(B+1)-A) / (A-1). Calculul lui A^(B+1) se face folosind acelasi algoritm mentionat mai sus in O(lg B) (lg = logaritm in baza 2). Pentru a efectua impartirea modulo 10^C, trebuie sa existe un invers multiplicativ pentru A-1 , modulo 10^C, lucru garantat doar pentru 50% din teste (cmmdc(A-1, 10^C) = 1). Inversul multiplicativ poate fi calculat folosind algoritmul [2]Euclid extins sau teorema lui Fermat: X^phi(N) = 1 (mod N) pentru cmmdc(X, N) = 1 si phi(N) = indicatorul lui Euler, cate numere < N sunt prime cu N. Din teorema reiese ca X^(phi(N)-1) = X^(-1) (mod N), asadar inversul poate fi calculat algoritmul de ridicare la o putere mentionat mai sus (phi(10^C) poate fi calculat usor). Un caz special la aceasta solutie apare atunci cand A = 1. Aceasta solutie n-ar fi adus decat 50p si necesita cunostiinte de matematica de clasa a 12-a. Exista o solutie mult mai accesibila pentru clasele a 10-a si a 11-a, folosind
Deoarece se cer doar ultimele $C$ cifre se va lucra modulo $10^C^$. Asadar, la primul pas se va calcula $A$ modulo $10^C^$, adica ne intereseaza doar ultimele $C$ cifre din $A$.
O prima solutie pentru a calcula $A^1^ + A^2^ + ... + A^B^$ este de calcula $A^i^$ in $O(lg i)$ pentru fiecare $i$ folosind algoritmul clasic de ridicare la o putere in numar logaritmic de pasi (Cormen, capitolul 33). Aceasta solutie ar fi adus doar $20p$.
Suma prezentata este o progresie geometrica clasica, si se poate calcula folosind formula $(A^B+1^-A) / (A-1)$. Calculul lui $A^(B+1)^$ se face folosind acelasi algoritm mentionat mai sus in $O(lg B)$ ({$lg$} = logaritm in baza 2). Pentru a efectua impartirea modulo $10^C^$, trebuie sa existe un invers multiplicativ pentru $A-1$ , modulo $10^C^$, lucru garantat doar pentru $50%$ din teste $(cmmdc(A-1, 10^C^) = 1)$. Inversul multiplicativ poate fi calculat folosind algoritmul Euclid extins sau teorema lui Fermat: $X^phi(N)^ = 1 (mod N)$ pentru $cmmdc(X, N) = 1$ si $phi(N)$ = indicatorul lui Euler, cate numere < $N$ sunt prime cu $N$. Din teorema reiese ca $X^phi(N)-1^ = X^-1^ (mod N)$, asadar inversul poate fi calculat algoritmul de ridicare la o putere mentionat mai sus ($phi(10^C^)$ poate fi calculat usor). Un caz special la aceasta solutie apare atunci cand $A = 1$. Aceasta solutie n-ar fi adus decat $50p$ si necesita cunostiinte de matematica de clasa a 12-a.
Exista o solutie mult mai accesibila pentru clasele a 10-a si a 11-a, folosind
relatiile:
S(A,2*B) = S(A,B) * (1+A^B)
S(A,2*B+1) = A * (1+S(A,2*B))
Cum numarul B este dat in baza 16, parcurgerea bitilor acestuia se face usor, simuland algoritmul de mai sus. Daca A^B se calculeaza la fiecare pas, complexitatea va fi O(lg^2 B), obtinand 60p. O solutie O(lg B) de 100 de puncte se poate obtine calculand in paralel si valorile S(A,B) si A^B. O ultima "problema" care ar fi putut exista este faptul ca se cer ultimele C cifre, nu rezultatul modulo 10^C; spre exemplu, daca C = 4 si rezultatul modulo 10^4 ar fi fost "123", in fisierul de iesire trebuia afisat "0123".
$S(A,2*B) = S(A,B) * (1+A^B^)$
$S(A,2*B+1) = A * (1+S(A,2*B))$
Cum numarul $B$ este dat in baza $16$, parcurgerea bitilor acestuia se face usor, simuland algoritmul de mai sus. Daca $A^B^$ se calculeaza la fiecare pas, complexitatea va fi $O(lg^2^ B)$, obtinand $60p$. O solutie $O(lg B)$ de $100$ de puncte se poate obtine calculand in paralel valorile $S(A,B)$ si $A^B^$. O ultima "problema" care ar fi putut exista este faptul ca se cer ultimele $C$ cifre, nu rezultatul modulo $10^C^$; spre exemplu, daca $C = 4$ si rezultatul modulo $10^4^$ ar fi fost $"123"$, in fisierul de iesire trebuia afisat $"0123"$.
h2. Distante minime
(problema usoara clasele 11-12)