Solutii Summer Challenge 2019

• Lista de probleme
• Cuvinte5
• Ultrapoligon
• Picazo
• Alambicare

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

Solutia problemei Ultrapoligon

Prerequisites : https://infoarena.ro/problema/aria

Solutia O((2^N) * N)

Luam fiecare subpoligon si calculam aria sa.
Pentru a calcula aria unui poligon vom lua pe rand punctele si vom adauga la suma 1/2 * (x[i] * y[i + 1] - x[i + 1] * y[i]).
De asemenea, deoarece la final se cere dublul ariei, putem adauga $(x[i] * y[i + 1] - x[i + 1] * y[i])$ direct.

Solutia O(N²)

Se observa ca aria unui poligon poate fi descompusa in muchii.
Acum putem calcula pentru fiecare muchie greutatea sa (x[i] * y[i + 1] - x[i + 1] * y[i]) si sa calculam in cate subpoligoane se afla.
Numarul de subpoligoane in care se afla muchia i,j cu i < j este 2 ^ (n - (j - i + 1)). Calculam intr-un mod asemanator si pentru muchiile cu j < i

Solutia O(N)

Se observa ca si aria unei muchii este compusa din 2 componente, anume:
x[i] * y[i + 1] si - x[i + 1] * y[i]
Vom rezolva pentru x[i] * y[i + 1] iar pentru cealalta se poate rezolva analog (Detaliu de implementare: eu am dat swap la x si y si am schimbat la final semnul)
Observam ca putem da factor comun pe x[i], mai intai vom calcula pentru i = 1 si obtinem:
x¹ * (y² * 2 ^{(n - 2) + y3 * 2} (n - 3) + ... y[n] * 2 ^{(n - n)).} Pentru a calcula pentru urmatorul i observam ca partea din paranteza se inmulteste cu 2 si se scade y[i] * 2 (n - 1) din ea.

Solutia problemei Picazo

Se observa faptul ca Picazo nu va cumpara niciodata aceeasi culoare si ca nu va picta de doua ori aceeasi celula.

Solutia O(2^N * (N + Q))

Incercam toate variantele si luam maximul.

Solutia O(N²)

Calculam bonus[i] = numarul de intervale care il contin pe i. Costul final pentru o configuratie este suma de bonus[i] - k pentru toate i-urile pictate + cate intervale contin cel putin o pozitie nepictata

De aici ne vine ideea sa folosim dinamica:
dp[i][j] = profitul maxim daca am rezolvat prefixul de lungime i unde ultima pozitie nepictata este j iar i + 1 este si el nepictat.
Acum avem recurentele

• dp[i][i] = max(dp[i - 1][j]) + numar de intervale care incep pe (i + 1) [j < i]
• dp[i][j] = dp[i - 1][j] + (bonus[i] - k) + numar de intervale care incep pe (i + 1) [j < i]

Insa recurenta nu este inca perfecta deoarece cand am pictat pozitia i s-au dezactivat niste intervale. Asa ca vom trece prin toate intervalele cu capatul dreapta in i si vom scadea 1 din toate dp[i][j] pentru care j < capatul stanga al lor.

Solutia O(N * logN)

Se observa ca putem folosi un arbore de intervale pentru a simula operatiile de la solutia precedenta

Solutia problemei Alambicare