potrivi.

h2. Lista lui Andrei

 
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$).

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 * Sigma^2), unde Sigma reprezinta marimea alfabetului (in cazul nostru 26).
 
 

Calcul

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".

h2. Distante minime

 
 
Distante minime
 

(problema usoara clasele 11-12)

Problema se rezolva folosind algoritmul lui Dijkstra pornind din nodul $1$. Astfel pe langa vectorul $D{~1..N~}$ in care tinem distantele minime vom mai folosi un vector $P{~1..N~}$ in care tinem pentru fiecare nod $i$ numarul de drumuri de lungime $D{~i~}$. Cand relaxam o muchie vom face update, daca este cazul, atat in vectorul $D$ cat si in vectorul $P$.

Problema se rezolva folosind algoritmul lui Dijkstra pornind din nodul 1. Astfel pe langa vectorul D[1..N] in care tinem distantele minime vom mai folosi un vector P[1..N] in care tinem pentru fiecare nod i numarul de drumuri de lungime D[i]. Cand relaxam o muchie vom face update, daca este cazul, atat in vectorul D cat si in vectorul P.
 
Deoarece costul drumurilor a fost definit ca produs de muchii, in vectorul D putem ajunge sa avem numere cu mii de cifre. O implementare cu numere mari a algoritmului descris mai sus nu este destul de eficienta, ea obtinand aproximativ 75 de puncte. Pentru a obtine punctajul maxim este necesara logaritmarea costului fiecarei muchii intr-o baza oarecare. Astfel putem transforma produsul in suma, folosind o proprietate a logaritmilor, fapt ce duce la o implementare simpla si rapida, folosind doar date de tip double.
 

Deoarece costul drumurilor a fost definit ca produs de muchii, in vectorul $D$ putem ajunge sa avem numere cu mii de cifre. O implementare cu numere mari a algoritmului descris mai sus nu este destul de eficienta, ea obtinand aproximativ $75$ de puncte. Pentru a obtine punctajul maxim este necesara logaritmarea costului fiecarei muchii intr-o baza oarecare. Astfel putem transforma produsul in suma, folosind o proprietate a logaritmilor, fapt ce duce la o implementare simpla si rapida, folosind doar date de tip $double$.

h2. Popandai
(problema grea clasele 11-12)