Revizia anterioară Revizia următoare
Solutii Happy Coding 2007 
Abc2
O prima abordare care ar parea sa aiba sanse de a obtine punctaj maxim este de a construi un trie al cuvintelor. Cu ajutorul acestui trie putem verifica in complexitate O(L) daca exista vreun cuvant care sa se termine la fiecare pozitie i din sir. Totusi, aceasta solutie are complexitate O(L*lungime text mare) si nu se incadreaza in timp.
Optimizarea consta in construirea automatului finit determinist asociat celor N cuvinte. Acest automat poate fi construit in complexitate O(N*L), conform algoritmului Aho-Corasick. Modul de constructie este asemanator calculului functiei prefix din algoritmul KMP. Construim trie-ul cuvintelor, apoi, pentru un nod X al trie-ului, determinam nodul din trie care corespunde celui mai lung sir de caractere care este sufix al sirului asociat nodului X. Putem calcula aceste valori pe nivele, intrucat un nod Y de tipul celui mentionat mai sus se va afla intotdeauna pe un nivel superior nodului X (dar nu neaparat pe calea de la radacina trie-ului pana la nodul X). Acest automat se poate folosi apoi in cadrul parcurgerii textului dat. Incepem din starea corespunzatoare sirului vid (radacina trie-ului). De fiecare data cand trecem la urmatorul caracter, incercam sa trecem in nodul din trie ce corespunde caracterului respectiv si este fiu al starii curente. Daca acest nod nu exista, la fel ca la KMP, trecem in starea corespunzatoare "prefixului-sufix" al starii curente si repetam acest lucru pana cand ajungem in radacina trie-ului sau intr-un nod care are un fiu ce corespunde caracterului urmator din sir. Daca ajungem intr-un nod ce corespunde unei stari finale, atunci am gasit o aparitie a unui cuvant.
Solutia oficiala foloseste un algoritm de constructie a unui automat finit determinist avand complexitate O(N*L2). Se va construi trie-ul cuvintelor, apoi, pe baza acestui trie, se va calcula un automat care are un numar de stari egal cu numarul de noduri ale trie-ului. Pentru fiecare stare X si fiecare caracter c, se va calcula functia nextState[X,c], reprezentand starea ce corespunde celui mai lung sir care este un subsir al sirului corespunzator starii X concatenat cu caracterul c. Pentru starile X ce au fiu in trie corespunzator unui caracter c, nextState[X,c] va fi egal cu acest fiu. Pentru celelalte caractere si o stare X, vom avea O(L) stari candidate. Mai exact, sa consideram ca TX este tatal nodului X in trie (presupunand ca X nu este radacina trie-ului) si ca avem starile Q0, Q1, .., QP stari ce corespund sufixelor de lungime 0, 1, .., P ale sirului corespunzator nodului TX (acest sir are P+1 caractere). Atunci multimea de stari R1, .., RP+1 avand aceeasi semnificatie pentru nodul X se calculeaza ca fiind R1=fiu[Q0,u], R2=fiu[Q1,u], .., RP+1=fiu[QP,u], unde X=fiu[TX,u], adica fiul nodului TX, ce corespunde caracterului u. La aceasta multime vom adauga pe R0=radacina trie-ului (ce corespunde sirului vid). nextState[X,c] va fi egal cu sirul de lungime maxima dintre sirurile corespunzatoare nodurilor fiu[Ri,c], cu 0 ≤ i ≤ P+1. Se observa usor ca pentru orice nod X pot exista cel mult O(L) stari candidate, deoarece sirul corespunzator unui nod X are O(L) caractere.
O solutie mai simpla si care ar obtine punctajul maxim consta in folosirea unor functii de hash, ca in algoritmului Rabin-Karp. Aceste functii trebuie sa fie calculabile usor (in O(1)) atunci cand avem valoarea hash-ului pentru un sir S si dorim sa calculam valoarea pentru sirul S' obtinut prin adaugarea unui caracter la dreapta lui S si inlaturarea unui caracter din stanga lui S. Cateva variante de functii de hash ar putea fi urmatoarele:
- functii polinomiale, cu puteri de numere prime: (cN*PN + cN-1*PN-1 + c1*P + c0) mod Q (P si Q numere prime)
- scrierea sirurilor ca numere in baza 3 (intrucat alfabetul consta doar din 3 litere) => este ideea de mai sus, dar cu P=3.
Probleme asemanatoare
Tritzi
Algoritm de complexitate O(N)
Vom calcula valorile T[i,j], reprezentand numarul de siruri de i tritzi, pentru care ultimul trit are valoarea j. T[1,j] = (1 mod P). Pentru i > 1, avem:
- T[i, 0] = (T[i-1, 0] + T[i-1, 2]) mod P
- T[i, 1] = (T[i-1, 1] + T[i-1, 2]) mod P
- T[i, 2] = (T[i-1, 0] + T[i-1, 1] + T[i-1, 2]) mod P
Aplicarea directa a acestor relatii de recurenta conduce la un algoritm liniar, care, insa, nu se incadreaza in limita de timp.
Algoritm de complexitate O(log N) - varianta 1
Folosind relatiile de recurenta de mai sus, putem construi o matrice A de iteratie si vom privi T[i] ca pe un vector coloana. Avem relatia: T[i] = A * T[i-1]. T[N] = AN-1 * T1. T1 este cunoscut direct, iar AN-1 se poate calcula in complexitate O(log N), folosind exponentiere logaritmica.
Algoritm de complexitate O(log N) - varianta 2
Vom calcula o matrice T[x][i][y] = numarul de siruri de tritzi (mod P), de lungime 2i si pentru care primul trit are valoarea x, iar ultimul trit are valoarea y. T[x]0[y] se determina direct, iar pentru i > 0, T[x][i][y] va fi egal cu o suma din T[x][i-1][a] * T[b][i-1][y], unde a si b sunt doua valori (0, 1 sau 2) care pot fi plasate una dupa alta.
Apoi vom scrie numarul N ca o suma de puteri ale lui 2: N = 2p1 + 2p2 + .. 2pK. Vom calcula o matrice U[x][i][y] = numarul de siruri de tritzi (mod P) de lungime 2p1 + 2p2 + .. + 2pi, pentru care primul trit are valoarea x si ultimul trit are valoarea y. Avem U[x]0[y] = T[x][p0][y]. Pentru i > 0, U[x][i][y] este egal cu o suma din U[x][i-1][a] * T[b][pi][y], unde a si b sunt doua valori de tritzi care pot fi plasate una dupa alta. Rezultatul final il vom obtine adunand toate valorile U[x][K][y], unde K este numarul de biti de 1 din reprezentarea binara a lui N.
h3.Probleme asemanatoare
Regine2
Problema se rezolva prin backtracking. Pentru fiecare pozitie (in ordinea liniilor si, pentru fiecare linie, in ordinea coloanelor), se incearca amplasarea sau neamplasarea unei regine in pozitia respectiva, iar apoi se marcheaza toate pozitiile atacate de regina respectiva, pentru a nu se mai incerca amplasarea unei regine viitoare pe o pozitie deja atacata. La intoarcerea din backtracking, pozitiile marcate se demarcheaza (vom folosi, de fapt, un contor pentru fiecare pozitie, in care vom retine de cate regine deja amplasate este atacata pozitia respectiva). Singura optimizare necesara este ca, atunci cand marcam pozitiile atacate de o regina nou-amplasata, vom marca doar pozitiile pe care vom incerca sa amplasam o regina in viitor (adica doar inspre directiile: est, sud-est, sud, sud-vest, si nu in toate cele 8 directii).
Probleme asemanatoare
Rfinv
Solutie de complexitate O(N4)
Vom sorta toate cele O(N2) distante din matrice in ordine crescatoare si vom initializa o matrice D[i][j]=infinit, pentru i <> j, respectiv 0, pentru i=j. Pe masura ce parcurgem sirul sortat al distantelor, vom actualiza valorile din matricea D. Sa presupunem ca am ajuns la o distanta avand valoarea x, ce reprezinta distanta minima dintre 2 noduri i si j. Daca D[i][j] < x sau D[i][j] > x si nu exista muchie in graf intre i si j, atunci nu avem solutie si ne oprim. Daca D[i][j] > x si exista muchie intre i si j, atunci vom pune pe aceasta muchie costul x. In continuare, va trebui sa actualizam valorile D[a][b] afectate de setarea valorii x pe muchia (i,j). Mai exact, pentru fiecare pereche de noduri (a,b), D[a][b] va fi egal cu minimul dintre valoarea actuala D[a][b] si min { D[a][i] + x + D[j][b], D[a][j] + x + D[i][b] }.
Daca nu am intalnit nici o contradictie pe masura ce am parcurs muchiile, atunci raspunsul este "DA" ; in caz contrar, raspunsul este "NU".
Solutie de complexitate O(N3)
Pe fiecare muchie a grafului (i,j) se pune o distanta egala cu valoarea A[i][j] ($A$ fiind matricea data). Se aplica apoi algoritmul Roy-Floyd pe acest graf, iar matricea distantelor obtinuta trebuie sa fie identica cu matricea distantelor data (in caz contrar neexistand solutie).
Probleme asemanatoare
Pali
Se va calcula pmin[i] = numarul minim de palindroame in care poate fi impartit sirul format din primele i caractere ale sirului dat.
Solutia 1
Vom avea pmin0 = 0 si pmin[i] = 1 + min { pmin[j] | subsirul j+1,..,i este un palindrom }, cu 0 ≤ j ≤ i-1. Pentru a determina rapid daca subsirul dintre 2 pozitii k si l este un palindrom, vom calcula o matrice Pali[k][l], avand valorile 1 si 0, daca subsirul dintre pozitiile k si l este palindrom sau nu. Vom avea Pali[k][l] = 1, daca sir[k] = sir[l] si Pali[k+1][l-1]=1 (pentru cazul in care l-k ≥ 2). Pentru ca aceasta solutie sa se incadreze in timp, va trebui ca matricea sa o calculam coloana cu coloana, pe masura ce avem nevoie de valorile din ea.
Solutia 2
Vom incerca sa calculam valorile pmin[i] treptat. Vom parcurge pozitiile de la 1 la N si vom incerca sa incepem un palindrom avand centrul in pozitia i (pentru cazul unui palindrom de lungime impara), respectiv avand centrul la pozitiile i si i+1 (pentru cazul unui palindrom de lungime para). Ideea importanta este ca, atunci cand ajungem la pozitia i, toate valorile pmin[j], cu j < i au fost calculate, iar valorile pmin[k], k > i, au niste valori partiale (adica valorile calculate nu sunt inca finale, ele mai putand sa scada ulterior). Vom extinde treptat cat putem de mult un palindrom in jurul pozitiei i (respectiv pozitiilor i si i+1); la fiecare pas de extindere, vom incerca sa incrementam palindromul de la lungimea curenta L, la lungimea L+2 (pentru aceasta verificam caracterele din capatele palindromului); inainte de a realiza extinderea, vom incerca sa folosim palindromul curent in cadrul unei solutii - mai exact, vom avea posibilitatea ca valoarea pmin[i-(L+1)/2]+1 sa fie folosita pentru a micsora valoarea lui pmin[i+(L+1)/2-1] (pentru cazul lungimii impare), respectiv valoarea pmin[i-L/2]+1 poate fi folosita pentru a micsora valoarea lui pmin[i+L/2] (pentru cazul lungimii pare).
Complexitatea ambelor solutii este O(N2), insa a doua solutie merge mai repede, in practica, deoarece ia in considerare numai palindroamele valide (care pot fi cel mult O(N2)).
Furnica
Flori2
Bitmap
Cascaval
Cercuri3
Antitero
Sistem2
Optic
Zvon
Solutia "oficiala" are complexitatea O(N*logN) si presupune calculul urmatoarelor valori:
- TMIN[i] = timpul minim necesar pentru a propaga zvonul in subarborele lui i, din momentul in care i afla zvonul. In mod clar, TMIN1 reprezinta rezultatul cautat.
Pentru a calcula TMIN[i], vom calcula intai valorile TMIN ale fiiilor lui i, pe care le vom sorta apoi descrescator: TMIN[f1] ≥ TMIN[f2] ≥ .. ≥ TMIN[fK]. Ordinea in care i va transmite zvonul fiilor sai este chiar ordinea descrescatoare a valorilor TMIN a acestora. In aceste conditii, TMIN[i] = maxim { 1 + TMIN[f1], 2 + TMIN[f2], .., K + TMIN[fK] }.
