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 de pe infoarena). 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, 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 gasim 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);

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

(NU STIU SA DEMONSTREZ LUCRURILE DE MAI SUS (rog pe cineva mai competent sa gaseasca o demonstratie))

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 folosite 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.

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