Note de curs, probleme algoritmică, 1 noiembrie 2013
În acest curs am discutat problema 1526 - Martian Plates.
Cerință
Câte parantezări corecte se pot realiza cu T paranteze, având la dispoziție N tipuri de paranteze și dându-se M restricții de tipul: în interiorul unei perechi de paranteze de tipul i nu se pot găsi paranteze de tipul j?
Rezolvare parțială 1
Câte parantezări corecte se pot realiza cu T paranteze, având la dispoziție un singur tip de paranteze și nicio restricție?
CT/2 (numerele lui Catalan)
Implementare
T /= 2;
Orice parantezare corectă de T perechi de paranteze începe cu o paranteză deschisă:
(...
Acesteia îi va corespunde o paranteză închisă:
(...)...
Această pereche de paranteze va delimita două secvențe de parantezări corecte care conțin împreună T - 1 perechi de paranteze.
Secv(T) = '(' + Secv(i) + ')' + Secv(T - i - 1), i = 0, 1, ..., T - 1
Pornind de la acest mod de construcție al secvențelor de parantezare putem scrie următorul algoritm:
const int MAX_T = 200; int Parantezari[MAX_T / 2 + 1]; int SOL; void solve() { Parantezari[0] = 1; for (i = 1; i <= T; ++i) { Parantezari[i] = 0; for (j = 0; i - j - 1 >= 0; ++j) { Parantezari[i] += Parantezari[j] * Parantezari[i - j - 1]; Parantezari[i] %= P; } } SOL = Parantezari[T]; }
Rezolvare parțială 2
Câte parantezări corecte se pot realiza cu T paranteze, având la dispoziție N tipuri de paranteze și nicio restricție?
NT/2 CT/2
Implementare
Pornind de la o parantezare corectă cu un singur tip de paranteze oarecare, se observă că:
- în locul unei paranteze deschise poate să apară oricare din cele N tipuri de paranteze disponibile;
- în locul unei paranteze închise trebuie să apară acel tip de paranteză corespunzător parantezei sale deschise;
Astfel, se observă că pentru fiecare paranteză deschisă se face câte o alegere independentă între N opțiuni, iar pentru fiecare paranteză închisă se face o alegere forțată (între o singură opțiune).
Îmbunătățind codul anterior, vom obține:
const int MAX_T = 200; int Parantezari[MAX_T / 2 + 1]; int SOL; void solve() { Parantezari[0] = 1; for (i = 1; i <= T; ++i) { Parantezari[i] = 0; for (j = 0; i - j - 1 >= 0; ++j) { for (k = 0; k < N; ++k) { Parantezari[i] += Parantezari[j] * Parantezari[i - j - 1]; Parantezari[i] %= P; } } } SOL = Parantezari[T]; }
În continuare, vom rezolva problema pentru toate submulțimile de tipuri de paranteze (deși momentan este inutil):
const int MAX_T = 200; const int MAX_N = 10; int Parantezari[MAX_T / 2 + 1][1 << MAX_N]; int Permisiune[MAX_N]; void solve() { for (i = 0; i <= N; ++i) { Parantezari[i][0] = 0; } for (l = 1; l < (1 << N); ++l) { Parantezari[0][l] = 1; for (i = 1; i <= T; ++i) { Parantezari[i][l] = 0; for (j = 0; i - j - 1 >= 0; ++j) { for (k = 0; k < N; ++k) if ((l & (1 << k)) > 0) { Parantezari[i] [l] += Parantezari[j] [l] * Parantezari[i - j - 1][l]; Parantezari[i][l] %= P; } } } } SOL = Parantezari[T][(1 << N) - 1]; }
Rezolvarea completă
Câte parantezări corecte se pot realiza cu T paranteze, având la dispoziție N tipuri de paranteze și dându-se M restricții de tipul: în interiorul unei perechi de paranteze de tipul i nu se pot găsi paranteze de tipul j?
Depinde de topologia grafului orientat care modelează restricțiile.
Implementare
Atunci când rezolvăm problema pentru o submulțime de tipuri de paranteze, trebuie să ținem cont de următoarele aspecte:
- prima paranteză deschisă trebuie să fie de unul din tipurile care fac parte din submulțimea pentru care facem calculele;
- secvența de după paranteza închisă poate conține doar aceeași submulțime de tipuri de paranteze;
- secvența dintre prima paranteză deschisă și perechea sa conține doar aceeași submulțime de tipuri de paranteze, restricționată la parantezele care sunt permise în interiorul tipului primei paranteze.
Secv(T, M) = '(' + Secv(i, M ∩ Permis('(')) + ')' + Secv(T - i - 1, M), i = 0, 1, ..., T - 1
Modificând implementarea anterioară, putem rezolva problema:
const int MAX_T = 200; const int MAX_N = 10; int Parantezari[MAX_T / 2 + 1][1 << MAX_N]; int Permisiune[MAX_N]; int P, T, N, M; int SOL; void read() { scanf("%d %d %d %d", &P, &T, &N, &M); T = T / 2; for (i = 0; i < N; ++i) { Permisiune[i] = (1 << N) - 1; } for (i = 0; i < M; ++i) { scanf("%d %d", &a, &b); --a; --b; Permisiune[a] ^= 1 << b; } } void solve() { for (i = 0; i <= N; ++i) { Parantezari[i][0] = 0; } for (l = 1; l < (1 << N); ++l) { Parantezari[0][l] = 1; for (i = 1; i <= T; ++i) { Parantezari[i][l] = 0; for (j = 0; i - j - 1 >= 0; ++j) { for (k = 0; k < N; ++k) if ((l & (1 << k)) > 0) { Parantezari[i] [l] += Parantezari[j] [l & Permisiune[k]] * Parantezari[i - j - 1][l]; // +k .... -k .... Parantezari[i][l] %= P; } } printf("%d %d = %d\n", i, l, Parantezari[i][l]); } } SOL = Parantezari[T][(1 << N) - 1]; }