h1(#Unlock). 'D. Unlock':problema/Unlock

?

Pentru rezolarea acestei probleme, vom folosi o structura de date speciala: o padure de multimi disjuncte care ne permite sa anulam ultimele operatii. Pentru realizarea acesteia, se retine o stiva cu operatiile facute.
Vom verifica pentru fiecare culoare daca este un unlocker. Vom creea o padure de multimi disjuncte cu anulari in care elementele nodurilor reprezinta spatiile matricii. Initial, toate spatiile libere vecine vor fi legate. Sa zicem ca culoarea pentru care verificam este c. Vom adauga toate spatiile de culoare c, legandu-le de vecinii de culoare c sau liberi. Verificam, apoi, daca o componenta care contine un spatiu liber le contine pe toate (pentru aceasta poate fi utilizata o stare suplimentara care contine numarul de spatii libere din multime). Daca da, atunci culoarea c este un unlocker, altfel nu. Observam ca adaugam si scoatem (prin anulare) fiecare element al matricii o data. Astfel, algoritmul are complexitatea O(n^2 * (comlexitate_uneste + complexitate_anuleaza)). Era suficienta pentru 100 de puncte o implementare cu complexitate_uneste = O(logn), complexitate_anuleaza = O(1).

h1(#MinMaxStore). 'E. MinMaxStore':problema/MinMaxStore