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?

C_T/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?

N^T/2 C_T/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];
}