h2. "PermutariAB":https://www.infoarena.ro/problema/permutariab

h2. "PermutariAB":https://www.infoarena.ro/problema/permutariab
 
Un lucru foarte interesant la această problemă este faptul că o putem reduce la a sorta crescător o permutare. Mai exact, vom transforma permutarea B într-o permutare Bt, astfel încât aplicând aceleaşi operaţii de swap, în aceeaşi ordine, necesare sortării în ordine crescătoare a permutării Bt pe permutarea B, să obţinem permutarea A. Acum rămâne de văzut cum construim permutarea Bt. Să ne uităm la permutarea A, să luam un indice 1 <= i <= N şi să constatăm că pe poziţia i se află o valoare x (i.e. A[i] = x). Deci după aplicarea operaţiilor de swap aferente transformării lui B în A, valoarea x trebuie să se afle pe poziţia i. Astfel, în Bt, pe poziţia j care are B[j] = x, în Bt vom pune valoarea i (i.e. Bt[j] = i), astfel spunându-ţi "Bă, eu vreau ca valoarea de pe poziţia j să ajungă pe poziţia i după efectuarea swap-urilor". Iar lucrul care face asta este ordonarea crescătoare a permutării Bt. În continuare, voi face afirmaţia că numărul minim de swap-uri necesar sortării permutării Bt este egal cu numărul de inversiuni ale permutării Bt, afirmaţie pe care am să o demonstrez în cele ce urmează. Readuc aminte faptul că o inversiune este o pereche de indici (i, j) cu i < j şi A[i] > A[j]. De aici rezultă ca numărul de inversiuni ale unei permutări sortate (permutarea identică) are 0 inversiuni şi este unica permutare cu 0 inversiuni. Să analizăm ce efecte are o operaţie de swap:
 
1) Dacă Bt[i] < Bt[i + 1] şi facem swap între ele, numărul de inversiuni va creşte cu 1.
2) Dacă Bt[i] > Bt[i + 1] şi facem swap între ele, numărul de inversiuni va scădea cu 1.
 
Evident că vom vrea să efectuăm swap-uri care vor scădea numărul de inversiuni, deoarece vrem să ajungem la 0 inversiuni cât mai repede. Şi deci cum un swap poate scădea cu maxim 1 numărul de inversiuni, rezultă că numărul minim de swap-uri necesare pentru a sorta permutarea este egal cu numărul de inversiuni ale permutării. Q.E.D.
Rămâne acum să vedem cum putem număra numărul de inversiuni. O primă soluţie ar fi chiar să observăm că algoritmul bubblesort rezolvă optim problema de mai sus şi sa aplicăm bubblesort pe Bt şi să numărăm numărul de swap-uri. Această soluţie are complexitate O(N ^ 2) şi ar trebui să obţină 70-80 de puncte.
Pentru 100p va trebui să numărăm inversiunile mai inteligent, folosind un arbore indexat binar/arbore de intervale sau algoritmul mergesort, însă ideile din spatele lor nu le voi mai prezenta în acest articol, ele putând fi găsite printr-o simplă căutare pe google.
 

h2. "PS":https://www.infoarena.ro/problema/ps
Problema se poate modela ca un graf bipartit in care cele doua multimi de noduri sunt reprezentate de elevi, respectiv de probleme, iar aparententa in tema sunt muchiile. Ce ramane de facut este sa vedem daca gasim o multime de muchii astfel incat toate nodurile apar o singur data. Daca o putem gasi, atunci aceasta este solutia in care un elev rezolva o singura tema. Altfel, putem afisa orice solutie simpla in care asociem problemele oricarui elev, caz in care un elev va rezolva $2$ probleme. O particularitate al grafului creat este ca gradul fiecarui nod este cel mult $2$. Partea de cuplaj poate fi rezolvata cu algoritmi clasici de cuplaj maxim in graf bipartit si se poate demonstra ca vor gasi solutia in timp $O(N)$. Totusi, aceasta parte se poate rezolva si mai simplu. Este clar ca putem include muchiile asociate unui nod de grad $1$ in multimea de cuplaj. Le alegem pe acestea si apoi le scoatem din graf. Este clar ca acest proces poate crea si alte noduri de grad $1$. Vom continua sa le adaugam in cuplaj. Cand se termina aceasta procedura, este clar ca toate nodurile ramase au grad $2$. Rezolvam pe rand aceste componente conexe. Acest tip de graf admite un cuplaj perfect trivial si il putem reduce la prima problema daca ne fixam o muchie pe care o adaugam in cuplaj.