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. 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 (în sensul că va da numărul minim de swap-uri) problema de mai sus, să 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.

Pudge

Putem observa ca Pudge cu cat arunca hook-ul mai in stanga de pozitia lui, timpul in care hook-ul ajunge pe axa Ox creste, deci inamicii se vor deplasa mereu mai spre dreapta decat erau inainte. Astfel, observam ca un inamic fixat intra in raza hook-ului la un punct (X1, 0) in care Pudge poate arunca hook-ul si iese din raza hook-ului la un punct (X2, 0), X2 <= X1, deci doar in intervalul [X2 + 1, X1] acest inamic va fi in raza hook-ului. Daca Pudge se afla in punctul (X, Y) si arunca hook-ul in punctul (X0, 0), timpul hook-ului sa ajunga pe axa Ox este , iar singurul termen care variaza din aceasta formula este X0. Astfel, pentru fiecare inamic vom cauta binar punctul X0 in care acesta intra in raza hook-ului si punctul X0 in care acesta iese din raza hook-ului, si vom creea un vector de evenimente de tipul (X, tip): daca tip e 1 inseamna ca de la pozitia X un inamic intra in raza hook-ului, iar daca tip e -1 inseamna ca de la pozitia X un inamic iese din raza hook-ului. Parcurgem acest vector de evenimente si vom sti la fiecare pas cati inamici prinde Pudge daca arunca hook-ul in punctul respectiv prin adunarea variabilelor "tip" din vector, iar raspunsul este maximul acestor valori.
(Atentie la cautarea binara deoarece pot exista erori de precizie din cauza radicalului, acestea pot fi rezolvate prin izolarea radicalului si ridicarea la patrat a inegalitatii pentru a scapa de acesta, sau putem lua un epsilon foarte mic pentru a verifica egalitatile)

Tenerife

Problema ne da un graf orientat aciclic unde nodurile sunt cluburile si muchiile sunt strazile dintre cluburui si ne cere sa calculam numarul de lanturi de cost 1. Costul unui lant este dat de cel mai mare divizor comun dintre valorile muchiilor de pe lant si o valoare K. Vom calcula numarul de lanturi de cost mai mare strict ca 1, deoarece vom vedea ca e mai usor sa calculam aceasta valoare, iar numarul de lanturi de cost 1 va fi numarul de lanturi posibile minus numarul de lanturi de cost mai mare strict ca 1.
Vom face sortarea topologica a grafului si numarul de lanturi posibile il vom calcula cu ajutorul programarii dinamice:

Dp[nod] = numarul de lanturi care incep din nod cu minim 2 noduri
Iar recurenta va fi: Dp[nod] = Suma din (Dp[vec] + 1), unde vec este un vecin al lui nod

Numarul de lanturi posibile este egal cu Suma din Dp[nod], pentru orice nod.
Acum trebuie sa calculam numarul de lanturi cu costul mai mare strict ca 1. Putem observa ca orice lant are costul egal cu cel mai mare divizor dintre (K, alte numere) => costul unui lant este divizibil cu cel putin un factor prim al lui K.
Pentru fiecare factor prim P al lui K putem calcula numarul de lanturi care au costul divizibil cu P, astfel vom afla numarul de lanturi cu costul mai mare strict ca 1. Pentru a nu lua in considerare un lant de mai multe ori ne vom folosi de principiul includerii si excluderii pe factorii primi distincti ai lui K.
Pentru o submultime de factori primi distincti ai lui K: P1, P2, .. , Pi vom calcula numarul de lanturi care au costul divizibil cu P1 * P2 * .. * Pi. Pentru a calcula acest numar vom face aceeasi dinamica ca inainte, doar ca vom folosi doar muchiile care au valoarea divizibila cu P1 * P2 * .. * Pi, acest lucru ne asigura faptul ca orice lant va avea costul divizibil cu P1 * P2 * .. *Pi.
Vom adauga sau vom scadea acest numar de lanturi gasit pentru o submultime fixata in functie de paritatea numarului de elemente al submultimii.
Rezultatul va fi = Numarul de lanturi posibile - Numarul de lanturi cu costul mai mare strict ca 1.