Solutii FMI No Stress 2012
Cercuri4
Solutie O(N2 + NlogN)
Se sorteaza cercurile descrescator dupa raza, deoarece un cerc cu o raza R nu poate fi inclus decat intr-un cerc cu o raza R1 >= R.Dupa sortare toate cercurile ce pot include cercul i se vor gasi inaintea acestuia.
Astfel putem aplica un algoritm asemanator celui de cel mai lung subsir crescator pentru a obtine frumusetea maxima, relatia de recurenta obtinuta fiind :
Fmax[ i ] = Frumusete[ i ] + max(Fmax[ j ] | j < i si cercul j include cercul i).
Pentru a verifica incluziunea a 2 cercuri (C1,R1) respectiv (C2, R2) urmatoarea relatie trebuie satisfacuta : distanta (C1,C2) + min(R1,R2) <= max(R1,R2). unde C reprezinta centrul cercului iar R raza .
Parantezare
Solutie O(M + LungimeaExpresiei)
Solutia foloseste o stiva St si un vector Poz ( acest vector retine pozitia parantezei ')' corespunzatoare parantezei '(' de pe pozitia i ).
Se parcurge sirul de intrare caracter cu caracter, pentru fiecare caracter verificandu-se tipul acestuia.
Daca sir[ i ] = '(' , atunci se adauga in stiva pozitia i
Daca sir[ i ] = ')' , se actualizeaza Poz[St[Varf]], deoarece paranteza ')' este paranteza ce corespunde celei de pe pozitia St[Varf].
Caractere care nu sunt paranteze se ignora .
Tamplar
Complexitate O(L) * nr_mari
Solutia problemei o reprezinta numarul (L - 1)!. Pentru calcularea acestui numar sunt necesare operatiile pe numere mari.
Invazie
Vmin
Potrivire
Solutie O(31*(N+M))
Fiecare subsecventa a sirului B, aflata intre 2 stelute o consideram un sir pentru care, folosind algoritmul KMP vom determina toate potrivirile acesteia in sirul A. Apoi, pe baza acestor rezultate se va construi solutia problemei, in asa fel incat pentru fiecare subsecventa a sirului B, aflata intre 2 stelute vom cauta cea mai din stanga potrivire in sirul A, dar in asa fel incat sa nu se suprapuna cu subsecventa anterioara.
Costperm
Solutie O(N*log N)
Fie sirul A, permutarea data.
Fiecare element A[k] va fi implicat intr-un numar Y de interschimbari, unde Y = numarul de elemente A[h], cu A[h]>A[k] si h<k. Evident costul unei interschimbari de acest gen va fi A[k]. Astfel, vom parcurge sirul A, pentru fiecare element A[k] vom afla Y si vom adauga la raspuns A[k]*Y.
Solutie alternativa O(N*log N) by 
Folosind algoritmul recursiv pentru Merge Sort, in timp ce sortam vectorul, actualizam valoarea costului astfel:
La pasul cand avem intervalul (a, b), luam contorul i intre a si (a + b) / 2; contorul j intre (a + b) / 2 + 1 si b.
Costul se va actualiza doar daca avem v[j] < v[i] atunci cand facem Merge Join-ul; atunci vom avea cost += v[j] * ((a + b) / 2 - i + 1).
Berarii2
Solutie O(M + N)
Se creaza graful transpus. Se parcurge in latime sau in adancime acest graf plecand din cele P noduri speciale. Se afiseaza nodurile pentru care viz[k]= 0.
