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

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.