Plicuri

Solutie: O(N * log N) - 100 puncte

Stim ca un plic i poate fi introdus intr-un plic j daca este adevarata una din urmatoarele conditii:

• L[i] < L[j] si W[i] < W[j]
• L[i] < W[j] si W[i] < L[j]

Cu alte cuvinte, putem spune ca un plic i poate fi introdus intr-un plic j daca este adevarata conditia:

• min(L[i], W[i]) < min(L[j], W[j]) && max(L[i], W[i]) < max(L[j], W[j])

Astfel, ca sa ne fie mai usor sa "comparam" doua plicuri in functie de dimensiunile acestora, vom retine pentru fiecare plic i, dimensiunea mai mica a sa in L[i], iar cealalta dimensiune in W[i]. Acum putem spune ca un plic i poate fi introdus intr-un plic j daca:

• L[i] < L[j] && W[i] < W[j]

Problema ne cere sa aflam lungimea maxima K a unui subsir de plicuri, astfel incat primul plic sa incapa in al doilea, al doilea in al treilea, ..., al K-1-lea in al K-lea. Intuitiv, aceasta cerinta ne duce cu gandul la un algoritm de tipul subsir crescator maximal. Pentru a aplica insa acest algoritm in cazul de fata, trebuie sa avem plicurile intr-o ordine convenabila. Vom sorta plicurile crescator dupa dimensiunea L a acestora, iar in caz de egalitate, descrescator dupa dimensiunea W. Astfel, pentru oricare doua plicuri i si j, cu i < j, vom avea doua cazuri:

• L[i] < L[j], deci este suficient sa comparam dimensiunea W ca sa ne dam seama daca plicul i poate fi introdus in plicul j.
• L[i] = L[j], deci W[i] > W[j], datorita conditiei de sortare in caz de egalitate. Deci este suficient sa comparam doar dimensiunea W a plicurilor pentru ne da seama ca plicurile nu pot fi introduse unul in celalalt.

Asadar, avand plicurile sortate dupa acest criteriu, pentru oricare doua plicuri i si j, este suficient sa comparam W[i] si W[j] pentru a ne da seama daca plicurile pot fi introduse unul in celalalt. In concluzie, putem aplica algoritmul de determinare a subsirului crescator maximal pe vectorul dimensiunii W a plicurilor, afisand lungimea determinata. Acest algoritm este explicat in detaliu la acest link: Scmax.