Solutii Runda 3

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

Alinuta

Problema este o generalizare a cazului cand K este egal mereu cu 0 (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

Dame 2

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.