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

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 $p{~i~} = q{~j~}$ unde {$z = p{~1~}^e{~1~}^&#0042; ... &#0042;p{~n~}^e{~n~}^$}, iar {$x = q{~1~}^f{~1~}^&#0042; ... &#0042;q{~m~}^f{~m~}^$}. Fie doua astfel de numere {$p{~i~} = q{~j~}$}. Noi trebuie sa afla suma tuturor numerelor care se divid cu $p{~i~}$ si sunt in intervalul [{$0, 2*x$}]. Aceste numere sunt : {$p{~i~}, 2&#0042;p{~i~}, ..., k&#0042;p{~i~}$}, {$0 < k &le; [2&#0042;x/p{~i~}]$}. Suma acestor numere se poate scrie ca {$p{~i~} + ... + k&#0042;p{~i~}$}, adica pi(1+...+k) adica {$p{~i~}&#0042;k(k+1)/2$}. De aici suntem tentati sa credem ca suma ceruta (fie aceasta {$S$}) este $S$ = {$x(2&#0042;x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - .... - p{~n~}&#0042;k{~n~}&#0042;(k{~n~}+1)/2$}. La o citire mai atenta observam ca am scazut unele de doua ori (cele care se divid si cu $p{~1~}$ si cu {$p{~2~}$}, 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 {$p{~1~}$}, $p{~2~}$ si {$p{~3~}$}, de exemplu). Astfel, aplicand principiul includerii si excluderii putem schita formula finala : {$S = x&#0042;(2x-1) - p{~1~}&#0042;k{~1~}&#0042;(k{~1~}+1)/2 - ... + p{~1~}&#0042;p{~2~}&#0042;k'{~1~}(k'{~1~}+1)/2 + ... - p{~1~}&#0042;p{~2~}&#0042;p{~3~}&#0042;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
h3. (problema grea, clasa a 10a)

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

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{~E{~1~}~} U f{~E{~2~}~} U ... U f{~E{~N~}~}|, 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{~E{~1~}~}| + |f{~E{~2~}~}| + ... + |f{~E{~N~}~}|$}
{$- |f{~E{~1~}~} ∩ f{~E{~2~}~}| - |f{~E{~1~}~} ∩ f{~E{~3~}~}| - ...$} (toate perechile)

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