Solutii FMI No Stress 2012

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 Stefan Eniceicu •Steve
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.

Fpwl