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

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.

h2. Pavare 2

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

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