h2. 'Itree':problema/itree
Un arbore este "arbore de intervale" (conform definitiei din enunt), numai daca orice nod are cel mult $2$ vecini al caror grad este mai mare decat $1$.
Un arbore este "arbore de intervale" (conform definitiei din enunt), numai daca fiecare nod are cel mult $2$ al caror grad este mai mare decat $1$.
h2. 'Hprob':problema/hprob
Se vor numerota cele $4!=24$ de permutari posibile ale celor $4$ obiecte cu numere de la $1$ la $24$. Se va calcula apoi o matrice $A$, unde fiecare element $A[i][j]$ reprezinta probabilitatea ca daca un client gaseste obiectele in starea $j$, acesta sa le puna la loc in ordinea corespunzatoare starii $i$. Vom considera ca, initial, obiectele a aflau in ordinea corespunzatoare starii $1$ si vom calcula probabilitatea ca la sfarsit acestea sa se afle tot in starea $1$. Vom privi matricea $A$ calculata ca o matrice de iteratie. Vom avea un vector $V{~i~}[j]$ reprezentand probabilitatea ca obiectele sa se afle in starea $j$ dupa $k$ iteratii. Putem calcula pe $V{~i~}$ ca fiind $A*V{~i-1~}$. In felul acesta, $V{~N~}=A^N^*V{~0~}$. $V{~0~}$ are valoarea $1$ pe pozitia $1$ si $0$ pe celelalte pozitii, iar $A^N^$ poate fi calculata eficient folosind exponentiere logaritmica.
Se vor numerota cele $4!=24$ de permutari posibile ale celor $4$ obiecte cu numere de la $1$ la $24$. Se va calcula apoi o matrice $A$, unde fiecare element $A[i][j]$ reprezinta probabilitatea ca daca un client gaseste obiectele in starea $j$, acesta sa le puna la loc in ordinea corespunzatoare starii $i$. Vom considera ca, initial, obiectele a aflau in ordinea corespunzatoare starii $1$ si vom calcula probabilitatea ca la sfarsit acestea sa se afle tot in starea $1$. Vom privi matricea $A$ calculata ca o matrice de iteratie. Vom avea un vector $V{~i~}[j]$ reprezentand probabilitatea ca obiectele sa se afle in starea $j$ dupa $k$ iteratii. Putem calcula pe $V{~i~}$ ca fiind $A*V{~i-1~}$. In felul acesta, $V{~N~}=A^N^*V{~0~}$. $V{~0~} are valoarea $1$ pe pozitia $1$ si $0$ pe celelalte pozitii, iar $A^N^$ poate fi calculata eficient folosind exponentiere logaritmica.
h2. 'Nodiv':problema/nodiv
h2. 'Arbore de cicluri':problema/arbciclu
Vom realiza urmatoarea operatie in mod repetat, pana cand operatia nu mai poate fi aplicata: daca exista un nod $i$ avand gradul $2$, iar vecinii acestuia sunt $j$ si $k$, eliminam nodul $i$ din graf si introducem muchia $j-k$, daca aceasta muchie nu exista deja. Daca graful dat este un arbore de cicluri, atunci la final trebuie sa ramanem cu doar $2$ noduri (si, initial, numarul de noduri trebuie sa fi fost cel putin $3$). Pentru a aplica operatia descrisa in mod eficient, vom folosi o coada in care vom introduce nodurile cu gradul $2$. De fiecare data cand extragem din coada un nod $i$, exista posibilitatea sa modificam gradele vecinilor acestuia, $j$ si $k$; daca $j$ sau $k$ ajunge sa aiba gradul $2$ in urma eliminarii lui $i$, il introducem si pe el in coada. Mai trebuie sa folosim o structura de date eficienta pentru a determina rapid daca $2$ noduri sunt adiacente, precum si pentru a elimina noduri din "lista" de adiacenta a altor noduri (in implementarea solutiei oficiale s-au folosit arbori echilibrati, prin intermediul structurii "set" din STL).
h2. 'Gandaci Java':problema/java
Problema cere determinarea unui cuplaj maxim intr-un graf bipartit. Algoritmii "standard" pentru determinarea unui cuplaj maxim sunt prea lenti pentru limitele date, de aceea este necesara folosirea unei optimizari, cunoscuta ca algoritmul 'Hopcoft-Karp':http://en.wikipedia.org/wiki/Hopcroft-Karp_algorithm ('aici':http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/123641 gasiti o implementare in Python a acestui algoritm).
