h2. 'Ndap':problema/ndap
...
Pentru fiecare submultime $V'$ a lui $V$, notam cu $E'$ multimea muchiilor care au ambele capete in $V'$, cu $NeConex[V']$ numarul subgrafurilor neconexe ale lui $V'$, iar cu $Conex[V']$ numarul subgrafurilor conexe ale lui $V'$. Se cunoaste faptul ca numarul total al subgrafurilor unui graf este egal cu $2^|E|^$, de aici rezultand egalitatea $Conex[V']$ = $2^|E'|^ - NeConex[V']$. Pentru fiecare sumbultime $V'$, vom incerca sa calculam {$NeConex[V']$}. Gasim un nod oarecare $X$ din $V'$. Pentru ca un subgraf al lui $V'$ sa fie neconex, componenta conexa din care face parte nodul $X$ trebuie sa fie diferita de $V'$. Vom genera toate submultimile $V$~$1$~ ale lui $V'$ din care face parte $X$ $(V$~$1$~ != $V'$). Consideram ca multimea $V$~$1$~ reprezinta componenta conexa din care face parte nodul $X$. Numarul de subgrafuri ale lui $V'$ avand fixata multimea $V$~$1$~ este egal cu produsul dintre numarul de subgrafuri conexe ale lui $V$~$1$~ si numarul total de subgrafuri ale lui $V$~$2$~ = $V'-V$~$1$~. Astfel, relatia de recurenta devine <tex> NeConex[V'] = \displaystyle\sum_{V_{1} \subset V'} Conex[V_{1}] * 2^{|E_{2}|} </tex>. Rezultatul il vom gasi in $Conex[V]$.
h2. 'Alinuta':problema/alinuta
...
Problema este o generalizare a cazului cand $K$ este egal mereu cu $0$ (problema 'pietre':problema/pietre). In cazul cand $K$ este $0$ stim ca exista anumite perechi $(a, b)$ de pietre care sunt pierzatoare. Primele perechi de acest gen sunt : $(1, 2)$, $(3, 5)$, $(4, 7)$, $(6, 10)$. Puteti sa verificati ca pentru aceste configuratii initiale primul jucator este pierzator orice ar face. Aceste perechi se pot genera dupa cateva observatii simple:
* diferenta intre termeni creste intodeauna cu $1$ ({$2 - 1 = 1$}; $3 - 5 = 2$; $7 - 4 = 3$; $6 - 10 = 4$)
* primul numar din fiecare pereche este cel mai mic numar natural strict pozitiv nefolosit inca in perechile anterioare ( $() -> 1$; $(1, 2) -> 3$; $(1, 2, 3, 5) -> 4$; $(1, 2, 3, 5, 4, 7) -> 6$).
Pe cazul general unde $K$ poate fi oricat ceea ce se schimba este diferenta intre termeni care creste cu $K + 1$ in loc de $1$ (primul subpunct) (cand $K$ este $0$ se verifica);
Tot ce ramane de facut este ca la inceput sa precalculam toate perechile $(a, b)$ pierzatoare pentru $K$-ul dat si sa vedem dupa aceea daca o anumita pereche data in fisierul de intrare se afla sau nu printre cele pierzatoare. Cum $A$, $B$ <= $100 000$ este clar ca pot fi cel mult $100 000$ de perechi. Ceea ce ne duce la o complexitate de $O(B)$ precalculare si apoi $O(1)$ pe query (pentru fiecare numar $x$ tinem minte perechea lui $y$ astfel incat $(x, y)$ este pierzator sau $0$ in caz ca nu exista acest $y$).
In general pentru problemele de acest tip in timpul concursului se observa regula cu ajutorul unei solutii brute force. In cazul acestei probleme solutia brute force presupunea calcularea unei matrici Win[x][y] = 1 daca (x, y) este castigatoare pentru primul jucator, 0 altfel.
Totusi, pentru cei care vor sa demonstreze ca algoritmul de mai sus functioneaza iata cateva observatii care va pot ajuta:
* $(a, b)$ si $(b, a)$ sunt echivalente
* daca $(a, b)$ este configuratie pierzatoare atunci orice $(a, c)$ cu $c > b$ este configuratie castigatoare; de aici rezulta imediat ca pentru un $a$ fixat avem un singur $b$ pentru care $(a, b)$ e pierzatoare restul configuratiilor de forma $(a, x)$ fiind castigatoare
h2. 'Dame 2':problema/dame2
...
Problema se rezolva prin metoda backtracking. Se iau toate posibilitatile de a aseza damele pe tabla de sah astfel incat oricare doua dame sa nu se atace. Ca sa intre in timp trebuiesc facute unele optimizari cum ar fi:
* atunci cand punem o dama marcam linia, coloana, prima diagonala si a doua dioagonala pe care este dama ca fiind ocupate pentru ca mai tarziu sa stim ca pe acestea nu putem pune alta dama (optimizam verificarea pentru a vedea daca putem sa punem o dama pe o anumita pozitie sau nu)
* tinem minte numarul minim de dame necesar gasit pana acum si in backtracking daca cumva trecem de acel numar cand cautam o solutie nu mai continuam pentru ca nu are sens (sigur am gasit o solutie cu numar de dame mai mic inainte) (initial acest numar este infinit)
* dupa ce am gasit o solutie cu un anumit numar de dame verificam daca fiecare patratel este atacat de o dama in $O(1)$ folosindu-ne de informatiile stiute de la primul subpunct, si anume: un patratel $(x, y)$ este atacat de o dama daca cel putin una din linia, coloana, prima diagonala, a doua diagonala sunt marcate ca fiind o dama pe ele.
