Problema se rezolva cu programare dinamica. Utilizam urmatoare structura de date:

* $V[i][j][0] *C$ numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie albe
* V[i][j][1] *C numarul de posibilitati pentru a pava i metri astfel incat primele j placi sa fie negre

* $V[i][j][0]$ = numarul de posibilitati pentru a pava $i$ metri astfel incat primele $j$ placi sa fie albe
* $V[i][j][1]$ = numarul de posibilitati pentru a pava $i$ metri astfel incat primele $j$ placi sa fie negre

Relatiile de recurenta sunt acum usor de dedus. Odata calculata matricea putem raspunde foarte usor primei cerinte, facand suma V[N][i][0] (pentru 1 <= i <= A) si V[N][i][1] pentru (1 <= i <= B).

Relatiile de recurenta sunt acum usor de dedus. Odata calculata matricea putem raspunde foarte usor primei cerinte, facand suma $V[N][i][0]$ (pentru {$1 ≤ i ≤ A$}) si $V[N][i][1]$ pentru ({$1 ≤ i ≤ B$}).

Pentru a 2-a cerinta incercam sa construim a K-a segventa lexicografica de la inceput catre sfarsit. Astfel, la fiecare pas incercam sa punem o segventa de tipul '0...01' care sa contina un numar maxim de '0'. Daca la pasul curent nu putem pune nici un '0' atunci vom pune o secventa de tipul '1..1' care sa contina un numar minim de 1. Numarul de '0'-uri sau de '1' pe care il punem il vom calcula cu ajutorul matricei precalculate la prima cerinta. Astfel, daca putem pune p de '0' inseamna ca numarul de posibilitati pentru a completa restul solutiei daca punem cel putin p de '0' la inceput este mai mare sau egal cu K. Alegem cel mai mare numar p cu proprietatea de mai sus. Daca p nu exista, incercam sa punem cat mai putini '1' in aceeasi maniera. Continuam apoi cu restul secventei, iar din K scadem numarul de solutii peste care am "sarit".

Pentru a 2-a cerinta incercam sa construim a {$K$}-a segventa lexicografica de la inceput catre sfarsit. Astfel, la fiecare pas incercam sa punem o segventa de tipul '{$0...01$}' care sa contina un numar maxim de '{$0$}'. Daca la pasul curent nu putem pune nici un '{$0$}' atunci vom pune o secventa de tipul '{$1..1$}' care sa contina un numar minim de {$1$}. Numarul de '{$0$}'-uri sau de '{$1$}' pe care il punem il vom calcula cu ajutorul matricei precalculate la prima cerinta. Astfel, daca putem pune $p$ de '{$0$}' inseamna ca numarul de posibilitati pentru a completa restul solutiei daca punem cel putin $p$ de '{$0$}' la inceput este mai mare sau egal cu {$K$}. Alegem cel mai mare numar $p$ cu proprietatea de mai sus. Daca $p$ nu exista, incercam sa punem cat mai putini '{$1$}' in aceeasi maniera. Continuam apoi cu restul secventei, iar din $K$ scadem numarul de solutii peste care am "sarit".
h2. Count

 
Count
 
(problema medie, clasele 11-12)

h3. (problema medie, clasele 11-12)

Inainte de a prezenta solutia, enumeram cateva propietati ale grafurilor planare care se vor dovedi utile mai departe:

1. Orice graf planar contine un nod cu grad mai mic decat 6
2. Numarul maxim de muchii pe care il poate avea un graf planar este 3 * N - 6, unde N este numarul de noduri. Asadar O(M)=O(N) (M fiind numarul de muchii).
3. Grafurile planare nu contin clici (subgrafuri complete) cu mai mult de 4 noduri (nu se poate desena in plan o clica de 5 noduri fara a intersecta muchiile acesteia).
 
Consecinta imediata a propietatii numarul 3 este ca intr-un graf planar vom avea clici de maxim 4 noduri. Cum cazurile in care clica cu numar maxim de noduri este compusa dintr-unul sau doua noduri este banal, ne vom concentra atentia pe cazurile in care avem clici de 3 sau 4 noduri.
 
Stiind acest lucru, un algoritm O(N^2) este usor de obtinut (si multi dintre concurenti au reusit acest lucru pentru ~70 de puncte). Ideea este urmatoarea:

# Orice graf planar contine un nod cu grad mai mic decat $6$
# Numarul maxim de muchii pe care il poate avea un graf planar este {$3 * N - 6$}, unde $N$ este numarul de noduri. Asadar $O(M)=O(N)$ ({$M$} fiind numarul de muchii).
# Grafurile planare nu contin clici (subgrafuri complete) cu mai mult de $4$ noduri (nu se poate desena in plan o clica de $5$ noduri fara a intersecta muchiile acesteia).

* Cazul clicilor de 3 noduri: se numara toate clicile care includ o anumita muchie incercand sa construim un triunghi impreuna cu fiecare nod din graf. Asadar pentru fiecare muchie, incercam cu fiecare nod (mai putin cele doua capete ale muchiei) sa construim o clica de 3 noduri. Complexitatea este O(M*N) = O(N^2) (folosindu-ne de propietatea 2). De altfel problema determinarii numarului de triunghiuri (clici de 3 noduri) intr-un graf, de aceasta data general, este cunoscuta si cea mai rapida rezolvare cunoscuta de noi este O(M*N / 32) daca pastram matricea de adiacenta pe biti - in total O(N^2 / 32) memorie. Va lasam pe voi sa descoperiti aceasta solutie iar daca nu reusiti cereti ajutor pe forum si vom completa acest articol.
* In cazul clicilor de 4 noduri, tot ce avem de facut este sa selectam doua muchii si sa vedem daca cele 4 capete ale lor formeaza o clica (presupunda ca avem 4 capete distincte). Acest algoritm are complexitatea O(M^2) = O(N^2)

Consecinta imediata a propietatii numarul $3$ este ca intr-un graf planar vom avea clici de maxim $4$ noduri. Cum cazurile in care clica cu numar maxim de noduri este compusa dintr-unul sau doua noduri este banal, ne vom concentra atentia pe cazurile in care avem clici de $3$ sau $4$ noduri.

Cum determinam, rapid, daca doua noduri sunt vecine? Solutia cea mai usoara este sa pastram matricea de adiacenta (eventual pe biti) si putem raspunde in O(1) la astfel de intrebari dar memoria este O(N^2). O alta idee care reduce marimea memoriei la O(M) este sa pastram listele de adicenta sub forma de hash-uri in loc de liste simple inlantuite (pentru cei care nu sunt familiari cu aceasta structura de date ii sfatuim sa citeasca articolele de pe devnet - sunt interesante si educative). Asadar, folosind hash-urile, memoria ramane O(M) dar putem afla rapid (aproape O(1)) daca doua noduri sunt vecine. In C++ aceasta structura de date este deja implementata sub numele de map, desi un query are complexitate logaritmica.

Stiind acest lucru, un algoritm $O(N^2^)$ este usor de obtinut (si multi dintre concurenti au reusit acest lucru pentru $~70$ de puncte). Ideea este urmatoarea:

Sa trecem la solutia O(N). Evident, vom folosi propietatea 1 (singura nefolosita pana acum). Din moment ce avem un nod cu grad mai mic decat 6, il identificam, generam toate clicile care il contin printr-un backtracking (dat fiind faptul ca sunt maxim 5 vecini) si il scoatem din graf. Graful rezultat este si el planar si cautam iar nodul cu grad mai mic decat 6, etc. Evident, nu vom face cautarea nodului de fiecare data - asta ar duce la un O(N^2), ci in momentul in care stergem un nod, verificam daca gradele vecinilor sai au scazut sub 6 si apelam o procedura recursiva cand gasim un astfel de vecin (un soi de DFS in graful dat). Dat fiind faptul ca backtracking-ul ruleaza in timp constant (desi e mare constanta) algoritmul acesta va avea complexitatea O(N) - presupunand ca putem raspunde in O(1) folosind hashurile daca doua noduri sunt vecine. Solutia noastra foloseste map-urile din STL asadar are complexitatea O(N*logN) cu o constanta considerabila (~100).

* Cazul clicilor de $3$ noduri: se numara toate clicile care includ o anumita muchie incercand sa construim un triunghi impreuna cu fiecare nod din graf. Asadar pentru fiecare muchie, incercam cu fiecare nod (mai putin cele doua capete ale muchiei) sa construim o clica de $3$ noduri. Complexitatea este $O(M*N) = O(N^2^)$ (folosindu-ne de propietatea {$2$}). De altfel problema determinarii numarului de triunghiuri (clici de $3$ noduri) intr-un graf, de aceasta data general, este cunoscuta si cea mai rapida rezolvare cunoscuta de noi este $O(M*N / 32)$ daca pastram matricea de adiacenta pe biti - in total $O(N^2^ / 32)$ memorie. Va lasam pe voi sa descoperiti aceasta solutie iar daca nu reusiti cereti ajutor pe forum si vom completa acest articol.
* In cazul clicilor de $4$ noduri, tot ce avem de facut este sa selectam doua muchii si sa vedem daca cele $4$ capete ale lor formeaza o clica (presupunda ca avem $4$ capete distincte). Acest algoritm are complexitatea $O(M^2^) = O(N^2^)$

Solutia de mai sus suporta multiple optimizari asupra factorului constant daca efectuam niste prepocesari inainte de algoritmul descris. Asadar, putem prepocesa pentru toate grafurile de maxim 6 noduri in care exista un nod conectat la toate celelalte, care este clica maxima si cate sunt. Nu sunt mai mult de 2^12 asemenea grafuri, deci prepocesarea va rula instantaneu. Avand aceasta informatie prepocesata, cand eliminam un nod din graful planar, in loc sa facem backtracking pentru a afla clicile maximale, interogam tabelul cu valorile prepocesate, optimizand factorul constant foarte mult (ajunge ~6). Totusi, nu era necesara implementarea acestor optimizari, din moment ce problema era media setului.

Cum determinam, rapid, daca doua noduri sunt vecine? Solutia cea mai usoara este sa pastram matricea de adiacenta (eventual pe biti) si putem raspunde in $O(1)$ la astfel de intrebari dar memoria este {$O(N^2^)$}. O alta idee care reduce marimea memoriei la $O(M)$ este sa pastram listele de adicenta sub forma de hash-uri in loc de liste simple inlantuite (pentru cei care nu sunt familiari cu aceasta structura de date ii sfatuim sa citeasca articolele de pe devnet - sunt interesante si educative). Asadar, folosind hash-urile, memoria ramane $O(M)$ dar putem afla rapid (aproape {$O(1)$}) daca doua noduri sunt vecine. In C++ aceasta structura de date este deja implementata sub numele de map, desi un query are complexitate logaritmica.
Sa trecem la solutia {$O(N)$}. Evident, vom folosi propietatea $1$ (singura nefolosita pana acum). Din moment ce avem un nod cu grad mai mic decat {$6$}, il identificam, generam toate clicile care il contin printr-un backtracking (dat fiind faptul ca sunt maxim $5$ vecini) si il scoatem din graf. Graful rezultat este si el planar si cautam iar nodul cu grad mai mic decat {$6$}, etc. Evident, nu vom face cautarea nodului de fiecare data - asta ar duce la un {$O(N^2^)$}, ci in momentul in care stergem un nod, verificam daca gradele vecinilor sai au scazut sub $6$ si apelam o procedura recursiva cand gasim un astfel de vecin (un soi de $DFS$ in graful dat). Dat fiind faptul ca backtracking-ul ruleaza in timp constant (desi e mare constanta) algoritmul acesta va avea complexitatea $O(N)$ - presupunand ca putem raspunde in $O(1)$ folosind hashurile daca doua noduri sunt vecine. Solutia noastra foloseste map-urile din STL asadar are complexitatea $O(N*logN)$ cu o constanta considerabila {$(~100)$}.
Solutia de mai sus suporta multiple optimizari asupra factorului constant daca efectuam niste prepocesari inainte de algoritmul descris. Asadar, putem prepocesa pentru toate grafurile de maxim $6$ noduri in care exista un nod conectat la toate celelalte, care este clica maxima si cate sunt. Nu sunt mai mult de $2^12^$ asemenea grafuri, deci prepocesarea va rula instantaneu. Avand aceasta informatie prepocesata, cand eliminam un nod din graful planar, in loc sa facem backtracking pentru a afla clicile maximale, interogam tabelul cu valorile prepocesate, optimizand factorul constant foarte mult (ajunge {$~6$}). Totusi, nu era necesara implementarea acestor optimizari, din moment ce problema era media setului.

Cowfood

h2. Cowfood

(problema grea, clasele 11-12)

h3. (problema grea, clasele 11-12)

Problema este bazata pe principiul includerii si excluderii. Constrangerile relativ mici ale problemei nu ar fi trebuit sa va pacaleasca sa incercati o cautare exhaustiva, intrucat aceasta ar fi obtinut numai 20-30% din punctaj.

Problema este bazata pe principiul includerii si excluderii. Constrangerile relativ mici ale problemei nu ar fi trebuit sa va pacaleasca sa incercati o cautare exhaustiva, intrucat aceasta ar fi obtinut numai $20-30%$ din punctaj.

Inainte de a trece la explicarea problemei, sa ne amintim principiul includerii si excluderii.

|A1 U A2 U ... U An| =
|A1| + |A2| + ... + |An|
- |A1 (U A2| - |A2 (U A3| - ... (toate perechile)
+ |A1 (U A2 (U A3| + ... (toate tripletele)

{$|A{~1~} U A{~2~} U ... U A{~n~}| =
|A{~1~}| + |A{~2~}| + ... + |A{~n~}|
- |A{~1~} ∩ A{~2~}| - |A{~2~} ∩ A{~3~}| - ... (toate perechile)
+ |A{~1~} ∩ A{~2~} ∩ A{~3~}| + ... (toate tripletele)

...

+ (-1)^(n-1) |A1 (U A2 (U ... (U An|

+ (-1)^(n-1)^ |A{~1~} ∩ A{~2~} ∩ ... ∩ A{~n~}|$}

Cum va fi folosit acesta? Vom calcula solutia ca fiind |multimea tuturor experimentelor valide| - |multimea experimentelor valide care sigur vor esua|. Sa notam aceasta multime de experimente cu F. Pentru orice experiment X, vom nota f(X) = multimea tutoror experimentelor care vor esua conform experimentului X.