Diferente pentru summer-challenge-2007/solutii/runda-3 intre reviziile #17 si #21

Nu exista diferente intre titluri.

Diferente intre continut:

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$<sub>$1$</sub> ale lui $V'$ din care face parte $X$ $(V$<sub>$1$</sub> != $V'$). Consideram ca multimea $V$<sub>$1$</sub> reprezinta componenta conexa din care face parte nodul $X$. Numarul de subgrafuri ale lui $V'$ avand fixata multimea $V$<sub>$1$</sub> este egal cu produsul dintre numarul de subgrafuri conexe ale lui $V$<sub>$1$</sub> si numarul total de subgrafuri ale lui $V$<sub>$2$</sub> = $V'-V$<sub>$1$</sub>. Astfel, relatia de recurenta devine <tex> NeConex[V'] = \displaystyle\sum_{V1 \subset V'} Conex[V1] * 2^{|E2|} </tex>. Rezultatul il vom gasi in $Conex[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
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

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.