Editorialul problemei Cuvinte5

Enunt:

Costul pentru a transforma un cuvant in altul este distanta levenstein² dintre cele doua cuvinte. Cate este costul minim de-a ajunge din A in B trecand prin K alte cuvinte dintr-un dictionar?

Subtask1:

Cuvintele din query fac parte din dictionar.
Pentru a calcula distanta dintre doua cuvinte, ne putem defini functia

Dist(A, B) = distanta levenstein²

Functia Dist este o dinamica simpla in O(lungime²).
Daca aveti neclaritati uitati-va pe articolul de pe Wikipedia (distanta levenstein este un concept foarte des intalnit care merita aprofundat).

Ne definim dinamica
dp[i][j][l] ca fiind costul minim de-a ajunge de la al i-lea cuvant la al j-lea cuvant trecand prim maxim l schimbari.

Recurenta poate fi calculata usor in O(n⁴):
dp[i][j]¹ = Dist(cuvant[i], cuvant[j]). Altfel spus, costul de-a ajunge de la al i-lea cuvant la al j-lea cuvant intr-un pas este din definitie Dist(al i-lea cuvant si al j-lea cuvant).

dp[i][j][l] unde l > 1 poate veni fie din dp[i][j][l - 1] daca decidem ca nu avem nevoie de a l-a mutare, fie din dp[i][q][l - 1] + dp[q][j]¹, unde 1 <= q <= n. Altfel spus, pentru a ajunge de la al i-lea cuvant la al j-lea cuvant in l mutari, trebuie sa facem o 'escala' la a (l-1)-a mutare, pe care putem sa o iteram.

Raspunsul pentru un Query este dp[id-ul lui A][id-ul lui B][K].

Complexitate:
O(N² * L² + N⁴ + Q * N)

Subtask2:

Cum K = N + 1 pentru toate cazurile, observam ca dinamica de la Subtaskul 1 poate fi transformata in dp[i][j] = cost minim de la i la j, care poate fi calculata in O(n³).

Rezolvarea subtaskurilor se rezolva ca la ultimul Subtask.

Complexitate:
O(N² * L² + N³ + Q * (N² + N * L²))

Subtask3:

Numarul de Queryuri este foarte mic.
Pentru fiecare Query, ne putem varia cuvantul din dictionar in care intram, si cuvantul din dictionar din care o sa iesim.
Apar cateva cazuri:

1. K = 1 => raspunsul este Dist(A, B).
2. K = 2 => raspunsul este min(cazul 1, Dist(A, X) + Dist(X, B)), unde X este un cuvant din dictionar.
3. K > 2 => raspunsul este min(cazul 1, Dist(A, X) + dp[X][Y][K - 2] + Dist(Y, B)), unde X si Y sunt cuvinte din dictionar.

Complexitate:
O(N² * L² + N⁴ + Q * (N² * L²))

Subtask4:

Solutia este similara cu Subtaskul 3, doar ca pentru fiecare Query ne precalculam Dist(A, X) si Dist(X, B) pentru totate cuvintele X din dictionar.

Complexitate:
O(N² * L² + N⁴ + Q * (N * L² + N²))
Factorul de N² * L² vine din precalcularea distantei dintre oricare doua cuvinte din dictionar.
Factorul de N⁴ vine din calcularea dinamici dp[i][j][l].
Factorul de Q * N * L² vine din calcularea distantei dintre cuvintele din query si cele din dictionar.
Factorul de Q * N² vine din calcularea intrarii si iesirii din dinamica (cazurile din subtasul 3).