h2. 'Ndap':problema/ndap

Avand o submultime $V$ a nodurilor si submultimea $E$ de muchii determinata de $V$ (muchiile care au ambele capete in $V$), trebuie sa calculam $nrCon[V]$ = numarul de subgrafuri conexe ale submultimei de noduri $V$. Observam ca ar fi mai usor sa calculam $nrNecon[V]$ = numarul de subgrafuri sigur neconexe ale submultimei de noduri $V$. Este clar ca numarul de subgrafuri ale submultimei de noduri $V$ va fi intotdeauna egal cu $2^|E|^$ ( prin $|E|$ intelegem modulul multimii $E$ ), deci $nrCon[V]$ va fi egal cu $2^|E|^ - nrNecon[V]$.

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$)

* 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 unui back.

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.

*Rog pe cineva sa scrie si o demonstratie a acestui algoritm*
Cateva observatii care sunt importante pentru demonstratie:

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 ca pentru un a fixat avem un singur $b$ pentru care $(a, b)$ e pierzatoare restul configuratiilor fiind castigatoare

* 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