Nu aveti permisiuni pentru a descarca fisierul grader_test3.in
Diferente pentru preoni-2006/runda-3/solutii intre reviziile #9 si #8
Nu exista diferente intre titluri.
Diferente intre continut:
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 ({$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~}$}.
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).
In acest moment putem sa ne dam seama de solutie
|F|=|f{~E{~1~}~}U f{~E{~2~}~}U ... U f{~E{~N~}~}|, care - conform principiului includerii si excluderii - este egal cu
|F| = |f(E1) U f(E2) U ... U f(EN)|, care - conform principiului includerii si excluderii - este egal cu
{$|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~}~}|$}
|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)|
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~}))$}.
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)).
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.
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.
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$ $m(i, 0) = 1$ $m(0,j) = 1$
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)$}.
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(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)$}.
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
