Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2007-09-23 14:15:54.
Revizia anterioară   Revizia următoare  

Solutii Runda 3

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

...

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; (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);

(NU STIU SA DEMONSTREZ LUCRURILE DE MAI SUS (se observa cu un back in timpul concursului :P) (rog pe cineva mai competent sa gaseasca o demonstratie))

Cateva observatii pentru demonstratie:
-- 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
-- (a, b) si (b, a) sunt echivalente

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.