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

{$|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~}|$}

{$|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

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

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

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