Solutii FMI No Stress 9

Freakadebunic

Pentru problema aceasta se puteau obtine 2 punctaje partiale: pentru 30p se ia fiecare pereche de noduri alese de Paula si pentru acestea se caulta LCA-ul (cel mai apropiat stramos comun) intr-un mod brut, urcand pe nivele; pentru 60p se va face LCA-ul cu RMQ. Solutia de 100 se bazeaza pe observatia: un nod este un LCA a 2 noduri marcate de Paula, daca acestea se afla in subarbori a 2 fii diferiti (+ cazul cand nodul actual este marcat de Paula; pentru a fi marcat si de Bunic, e necesar ca un singur subarbore al unui fiu sa contina nod marcat de Paula). Complexitatea este O(N), putand calcula pentru fiecare nod cati subarbori ai fiilor au noduri marcate de Paula printr-un DFS. 

Hagi

Prima observatie este faptul ca distribuirea golurilor nu este legata de distribuirea asisturilor. Problema ne cere practic numarul de partitionari diferite ale golurilor, respectia ale asisturilor, iar raspunsul este produsul acestor 2 partitionari. Daca vrem sa distribuim N goluri la K echipe, vom avea combinari de N+K-1 luate cate K-1 (aceeasi logica pentru asisturi). Puteti gasi mai multe despre aceasta formula cautand pe un motor de cautare "stars and bars combinatorics".

Pandemie

Pentru a obtine 100 de puncte este necesara o implementare in O(NlogN) sau log patrat bine implementata.
Prima solutie necesita aplicarea Heavy Path Decomposition. Vom vrea sa aflam pentru o operatie de tip 3 pentru nod_actual, cel mai apropiat nod virusat de nod_actual pe lantul radacina - nod_actual. Pentru o operatie de tip 1, vom updata valoarea nodului cerut cu valoarea nivelului pe care se afla nodul, iar pentru o operatie de tip 2, vom updata valoarea cu 0. Pentru a afla raspunsul la operatia de tip 3, vom avea nevoie de nodul cu cea mai mare valoare de pe lantul radacina - nod_actual, acel nod se va afla "cel mai jos", adica cel mai aproape de nod_actual. Putem afla nodul: daca tinem un pair pentru fiecare nod in heavy (valoarea uptatata, respectiv id-ul nodului) sau aplicand jmenul de la stramosi ca sa aflam nodul respectiv dupa ce aflam la ce nivel se afla.
A doua solutie presupune liniarizarea arborelui. Pentru operatia de tip 1 vom marca nodul cu 1, iar pentru operatia de tip 2 vom marca nodul cu valoarea 0. Nodul cerut pentru operatia 3 va fi cel mai indepartat nod de nod_actual pentru care suma de pe lantul nod_cautat - nod_actual este 0. Vom cauta binar al catelea stramos este nod_cautat, vom calcula cu un aint sau un aib suma de pe lant. In final vom aplica jmenul de la stramosi pentru a afla raspunsul.

Operatie

Metoda 1:
Observam ca numerele de pe pozitiile impare sunt practic date in input (w[2*k+1][2*k+1] = v[2*k+1][2*k+1] = v[2*k+1]). Ne ramane sa determinam numerele de pe pozitiile pare. In continuare vom arata cum se poate determina v[0].

Vom afla pe rand toti bitii lui v[0]. Pentru inceput ne vom baza de implicatia v[0] -> v[1] = w[0][1]. Stim ca daca bitul de la pozitia i al lui v[1] este 0, atunci bitul lui v[0] de la pozitia i va fi egal cu negatia bitului de la pozitia i al lui w[0][1] (din legea dupa care functioneaza implicatia logica). Daca bitul de la pozitia i al lui v[1] este 1, atunci stim doar ca bitul lui w[0][1] nu poate fi 0. In cazul in care acest lucru se intampla afisam -1.
Analog luam in calcul implictia v[1] -> v[0] = w[1][0]. Daca bitul de la pozitia i al lui v[1] este 1, atunci bitul lui v[0] de la pozitia i va fi egal cu bitul de la pozitia i al lui w[1][0] (tot din legea implicatiei logice). Daca bitul de la pozitia i al lui v[1] este 0, iar cel al lui w[1][0] este 0 vom afisa -1.

Observam ca prima implicatie ne determina in mod unic bitii lui v[0] ai caror corespondenti in v[1] sunt 0. A doua implicatie determina in mod unic bitii lui v[0] ai caror corespondenti in v[1] sunt 1. Prin urmare stim ca exista un singur numar v[0] care satisface implicatiile de mai sus. Astfel stim ca problema are cel mult o solutie.
Dupa ce aflam analog toate numerele de pe pozitiile pare mai trebuie doar sa verificam daca solutia este valida (este posibil sa nu respecte operatiile de xor sau sa nu respecte alte implicatii in afara de cele cu v[1]).
Complexitate: O(N^2 + N * B)

Metoda 2:
Observam ca este suficient sa aflam doar primele 4 numere. Restul se pot deduce pe baza operatiilor de xor. De exemplu: v[4*k] = w[0][4*k] ^ v[0].
Putem determina numerele bit cu bit. Pentru fiecare pozitie avem 2^4 = 16 modalitati de a alege bitii de pe pozitia respectiva ai primelor 4 numere. Pentru fiecare modalitate generam bitii pentru celelalte N numere (folosind regula de mai sus) si verificam daca formeaza o solutie valida.
Complexitate: O(N^2 * B). Solutia se va incadra in timp datorita constantei relativ mici.

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". 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. Astfel se obţine complexitatea dorită O(NlogN). De menţionat că şi o soluţie în O(Nsqrt(N))) ia punctaj maxim.

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.