h1. Solutii preONI 2006 - Runda a 3-a

(Categoria _Competitii_, autor(i) _Echipa info-arena_)

(Categoria _Competitii_, autor(i) _Echipa infoarena_)

Runda a 3-a concursului preONI 2006 s-a incheiat. Acest articol va prezinta solutiile oficiale ale celor 7 probleme propuse precum si cateva aprecieri pe marginea concursului.

h3. (problema medie, clasa a 9a)

Fiind vorba de maxim $1.000.000$ numere se poate calcula pentru fiecare in parte cati divizori primi are. Pentru acest lucru se foloseste ciurul lui Erathostene si se construieste vectorul {$ndp{~i~}$} - numarul de divizori primi ai lui {$i$}. Parcurgem numerele din $1$ in $1$ si in momentul in care am dat peste un numar care are $0$ divizori primi pana in acest moment inseamna ca am gasit un nou numar prim si vom actualiza vectorul $ndp$ pentru toti multiplii lui si implicit pentru el (numarul fiind propriul sau divizor). Apoi se construieste o matrice $sol{~i,j~}$ care retine care este cel mai mare numaru mai mic sau egal cu $i$ cu $j$ divizori primi (adica exact raspunsurile pentru problema noastra). Pentru a construi linia $i$ se copiaza linia $i-1$ si se actualizeaza {$sol{~i,ndp{~i~}~}=i$}.

Fiind vorba de maxim $1.000.000$ numere se poate calcula pentru fiecare in parte cati divizori primi are. Pentru acest lucru se foloseste ciurul lui Erathostene si se construieste vectorul {$ndp{~i~}$} - numarul de divizori primi ai lui {$i$}. Parcurgem numerele din $1$ in $1$ si in momentul in care am dat peste un numar care are $0$ divizori primi pana in acest moment inseamna ca am gasit un nou numar prim si vom actualiza vectorul $ndp$ pentru toti multiplii lui si implicit pentru el (numarul fiind propriul sau divizor). Apoi se construieste o matrice $sol{~i,j~}$ care retine care este cel mai mare numar mai mic sau egal cu $i$ cu $j$ divizori primi (adica exact raspunsurile pentru problema noastra). Pentru a construi linia $i$ se copiaza linia $i-1$ si se actualizeaza {$sol{~i,ndp{~i~}~}=i$}.

Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa "articolul":http://infoarena.ro/Ciurul_lui_Erathostene.

Pentru mai multe detalii despre cum functioneaza ciurul lui Erathostene puteti accesa "articolul":http://infoarena.ro/Ciurul-lui-Erathostene.

h2. Subsir 2

h3. (problema grea clasa a 9a, problema medie clasa a 10a, problema usaora clasele 11-12)

h3. (problema grea clasa a 9a, problema medie clasa a 10a, problema usoara clasele 11-12)

Problema poate fi considerata asemanatoare cu cea a celui mai lung subsir crescator, avand o rezolvare similara de complexitatea $O(N^2^)$ folosind metoda programarii dinamice.

Vom face o prima observatie:

* $(n, d) = 1 <=> (n, n - d) = 1, (n, n + d) = 1 $

* $(n, d) = 1 <=> (n, n - d) = 1, (n, n + d) = 1$

Fie {$a = phi (n)$}, indicatorul lui Euler. Fie $b$ numarul de numere prime cu $n$ cuprinse intre $n$ si {$2 * n$}.
Deoarece {$(n, d) = 1 <=> (n, n + d) = 1, a &le; b$}. Deoarece {$(n, d) = 1 <=> (n, n - d) = 1, b &le; a => b = a$}. Fie {$x{~1~}, x{~2~}, .. x{~a~}$} numerele $< n$ si prime cu $n$ => numerele cuprinse intre $n$ si $2 * n$ si prime cu $n$ vor fi {$x{~1~} + n, x{~2~} + n, .. x{~a~} + n$}.
Conform observatiei facute, $(n, n - x{~1~}) = 1, (n, n - x{~2~}) = 1, .. (n, n - x{~a~}) = 1$ =>

x{~a~} = n - x{~1~} <=> x{~1~} + x{~a~} = n
x{~a-1~} = n - x{~2~} <=> x{~2~} + x{~a-1~} = n

$x{~a~} = n - x{~1~} <=> x{~1~} + x{~a~} = n$
$x{~a-1~} = n - x{~2~} <=> x{~2~} + x{~a-1~} = n$

...

x{~1~} = n - x{~a~} <=> x{~a~} + x{~1~} = n

$x{~1~} = n - x{~a~} <=> x{~a~} + x{~1~} = n$

Fie $S1$ suma numerelor prime cu $n$ si mai mici ca {$n$}, fie $S2$ suma numerelor prime cu {$n$}, cuprinse intre $n$ si {$2 * n$}.
Adunand cele a egalitati, obtinem $2 * S1 = a * n$ => {$S1 = (a * n) / 2$}.
$S2 = a * n + S1$ => {$S1 + S2 = 2 * a * n$}.

Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta "articolul":http://infoarena.ro/Ciurul_lui_Erathostene despre cirulul lui Erathostene.

Se foloseste o singura data ciurul lui Erathostene pentru a determina functia phi pentru toate intrebarile. Se poate consulta "articolul":http://infoarena.ro/Ciurul-lui-Erathostene despre cirulul lui Erathostene.

O alta solutie, propusa de Bogdan A. Stoica, se bazeaza pe principul includerii si excluderii. Din enuntul problemei ne dam seama ca suma ceruta este suma tuturor numerelor z cu proprietatea ca cmmdc(z, x) = 1. Pentru a afla aceste numere este de ajuns sa observam ca cmmdc(z, x) != 1 daca si numai daca exista cel putin un pi = qj unde z = p1^e1*...*pn^2n, iar x = q1^f1*....*qm^fm. Fie doua astfel de numere pi = qj. Noi trebuie sa afla suma tuturor numerelor care se divid cu pi si sunt in intervalul [0, 2*x]. Aceste numere sunt : pi, 2*pi, ..., k*pi, 0 < k <= [2*x/pi]. Suma acestor numere se poate scrie ca pi +....+ k*pi, adica pi(1+...+k) adica pi*k(k+1)/2. De aici suntem tentati sa credem ca suma ceruta (fie aceasta S) este S = x(2*x-1) - p1*k1*(k1+1)/2 - .... - pn*kn*(kn+1)/2. La o citire mai atenta observam ca am scazut unele
de doua ori (cele care se divid si cu p1 si cu p2, de exemplu) si nu am scazut deloc alte numere care au un divizor comun cu x mai mare decat 1 (cele care se divid simultan cu p1, p2 si p3, de exemplu). Astfel, aplicand principiul includerii si excluderii putem schita formula finala : S = x*(2x-1) - p1*k1*(k1+1)/2 - ... + p1*p2*k'1(k'1+1)/2 + ... - p1*p2*p3*k''1(k''1+1)/2 + ..., adica vom scadea toti termenii care se obtin prin inmultirea a unui numar impar de factori primi si vom aduna restul. Aceasta solutie obtine in jur de 80 de puncte pe restul testelor depasind timpul de executie.

h2. Pavare 2

 
 
Pavare 2
 
(problema grea, clasa a 10a)

h3. (problema grea, clasa a 10a)

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

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

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:

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.

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

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:

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.

* 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^)$

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

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.

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.

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.
h2. Cowfood

Cowfood

h3. (problema grea, clasele 11-12)

(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)
...
+ (-1)^(n-1) |A1 (U A2 (U ... (U An|

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

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

Astfel, pentru un experiment A de forma (a1, a2, ..., aK) si orice experiment B = (b1, b2, ..., bK) cu a1=<b1, a2=<b2, ..., aK=<Bk, B apartine f(A).

Astfel, pentru un experiment $A$ de forma ({$a{~1~}, a{~2~}, ..., a{~K~}$}) si orice experiment $B$ = ({$b{~1~}, b{~2~}, ..., b{~K~}$}) cu {$a{~1~} ≤ b{~1~}$}, {$a{~2~} ≤ b{~2~}$}, ..., {$a{~K~} ≤ b{~K~}$}, $B$ apartine {$f{~A~}$}.

In acest moment putem sa ne dam seama de solutie

|F| = |f(E1) U f(E2) U ... U f(EN)|, care - conform principiului includerii si excluderii - este egal cu

$|F| = |f{~E{~1~}~} U f{~E{~2~}~} U ... U f{~E{~N~}~}|$, care - conform principiului includerii si excluderii - este egal cu

|f(E1)| + |f(E2)| + ... + |f(EN)|
- |f(E1) (U f(E2)| - |f(E1) (U f(E3)| - ... (toate perechile)
+ |f(E1) (U f(E2) (U f(E3)| ... (toate tripletele)
...
+ (-1)^(n-1) |f(E1) (U f(E2) (U ... (U f(EN)|

{$|f{~E{~1~}~}| + |f{~E{~2~}~}| + ... + |f{~E{~N~}~}|$}
{$- |f{~E{~1~}~} ∩ f{~E{~2~}~}| - |f{~E{~1~}~} ∩ f{~E{~3~}~}| - ...$} (toate perechile)
{$+|f{~E{~1~}~} ∩ f{~E{~2~}~} ∩ f{~E{~3~}~}| ...$}(toate tripletele)
{$...$}
{$+(-1)^n-1^ |f{~E{~1~}~} ∩ f{~E{~2~}~} ∩ ... ∩ f{~E{~N~}~}|$}

Ce reprezinta intersectia ("(U") in acest context?
Daca A = (a1, a2, ..., aK) si B = (b1, b2, ..., bK), A (U B va fi multimea ce contine toate experimentele despre care se stie cu siguranta ca vor esua, atat conform lui A cat si lui B. Altfel spus, A (U B = multimea experimentelor care vor esua conform (max(a1, b1), max(a2, b2), ..., max(aK, bK)).

Ce reprezinta intersectia ("∩") in acest context?
Daca $A = (a{~1~}, a{~2~}, ..., a{~K~})$ si {$B = (b{~1~}, b{~2~}, ..., b{~K~})$}, $A ∩ B$ va fi multimea ce contine toate experimentele despre care se stie cu siguranta ca vor esua, atat conform lui $A$ cat si lui {$B$}. Altfel spus, $A ∩ B$ = multimea experimentelor care vor esua conform {$(max(a{~1~}, b{~1~}), max(a{~2~}, b{~2~}), ..., max(a{~K~}, b{~K~}))$}.

Un ultim lucru care trebuie obinut este calcularea lui |f(X)| pentru orice X = (x1, x2, ... xK). Pentru a obtine un experiment esuat, putem incrementa toate valorile xi atata timp cat suma lor este =< S. Astfel avem |f(X)| = m(S - (x1 + x2 + ... + xK), K), unde m(i, j) reprezinta numarul de posibilitati de a aranja cel mult i bile identice in j cutii diferite.

Un ultim lucru care trebuie obinut este calcularea lui |f{~X~}| pentru orice {$X = (x{~1~}, x{~2~}, ... x{~K~})$}. Pentru a obtine un experiment esuat, putem incrementa toate valorile x{~i~} atata timp cat suma lor este ≤ {$S$}. Astfel avem |f{~X~}| = {$m(S - (x{~1~} + x{~2~} + ... + x{~K~}), K)$}, unde $m(i, j)$ reprezinta numarul de posibilitati de a aranja cel mult $i$ bile identice in $j$ cutii diferite.

Aceasta se calculeaza simplu folosind recurenta care nu va fi demonstrata aici

m(i, j - 1) = p(i, j) = p(i - 1, j) + p(i, j - 1), i, j > 0
1 , i = 0 sau j = 0
 
cu p(i, j) = numarul de posibilitati de a aranja exact i bile identice in j cutii diferite. Valorile m(i, j) se preproceseaza la inceput intr-o matrice, in timp O(K*S).
 
O implementare bruta a problemei va duce la complexitatea O(KS + 2^N*N*K), dar aceasta ar obtine numai 60% din punctajul maxim. O implementare inteligenta folosind preferabil o functie recursiva care exploreaza toate submultimile celor N experimente si la fiecare pas actualizeaza solutia in O(K) obtine cu usurinta 100 de puncte. Complexitatea sa este O(K*S + 2^N*K).

$m(i, j - 1) = p(i, j) = p(i - 1, j) + p(i, j - 1), i, j > 0$
$m(i, 0) = 1$
$m(0,j) = 1$

References

cu $p(i, j)$ = numarul de posibilitati de a aranja exact $i$ bile identice in $j$ cutii diferite. Valorile $m(i, j)$ se preproceseaza la inceput intr-o matrice, in timp {$O(K*S)$}.

Visible links
1. http://info.devnet.ro/articole.php?page=art&art=30
2. http://info.devnet.ro/articole.php?page=art&art=30

O implementare bruta a problemei va duce la complexitatea $O(K*S + 2^N^*N*K)$, dar aceasta ar obtine numai $60%$ din punctajul maxim. O implementare inteligenta folosind preferabil o functie recursiva care exploreaza toate submultimile celor $N$ experimente si la fiecare pas actualizeaza solutia in $O(K)$ obtine cu usurinta $100$ de puncte. Complexitatea sa este {$O(K*S + 2^N^*K)$}.