h2(#grozavesti). 'Grozavesti':problema/grozavesti

Observam ca daca avem la dispozitie o matrice $NxN$ putem aduce orice element pe pozitia $(1,1)$ in cel mult doua interschimbari (una pentru linii si una pentru coloane). Daca elementul minim se afla pe pozitia $(i,j)$ interschimbam linia $i$ si coloana $j$ cu linia $1$ si coloana $1$. Astfel pentru fiecare $x$ de la $1$ la $N$ vom plasa pe pozitia $(x,x)$ cel mai mic element din submatricea avand coltul stanga sus $(x,x)$. Acum problema se reduce la aflarea elementului minim din submatricea avand coltul stanga sus $(x,x)$. Se poate implementa direct acest pas iterand prin toate valorile posibile si se obtine un algoritm de complexitate $O(N^3^)$. Exista un algoritm mai bun, de complexitate $O(N^2^logN)$ folosind un max-heap in care sunt introduse elementele din matrice, la fiecare interschimbare de linii sau coloane fiind actualizate elementele din max-heap.

Observam ca daca avem la dispozitie o matrice $NxN$ putem aduce orice element pe pozitia $(1,1)$ in cel mult doua interschimbari (una pentru linii si una pentru coloane). Daca elementul minim se afla pe pozitia $(i,j)$ interschimbam linia $i$ si coloana $j$ cu linia $1$ si coloana $1$. Astfel pentru fiecare $x$ de la $1$ la $N$ vom plasa pe pozitia $(x,x)$ cel mai mic element din submatricea avand coltul stanga sus $(x,x)$. Acum problema se reduce la aflarea elementului minim din submatricea avand coltul stanga sus $(x,x)$. Se poate implementa direct acest pas iterand prin toate valorile posibile si se obtine un algoritm de complexitate $O(N^3^)$. Daca in loc sa ne uitam la toata submatricea, verificam doar valorile de pe diagonala principala din submatrice obtinem complexitatea $O(N^2^)$, dar acest lucru nu era necesar pentru obtinerea punctajului maxim.