Astfel, cand se ajunge la un {$j$}, se verifica inainte daca {$V{~j~} < min$} (conditie necesara pentru a construi un sir maximal). Un ultim detaliu in solutie este obtinerea solutiei minime din punct de vedere lexicografic. Cand se selecteaza {$j$}-ul pentru fiecare {$i$}, pe langa faptul ca se alege acela cu $A{~j~}$ minim, in caz de egalitate se va alege acela cu valoarea $V{~j~}$ minima. Selectarea este corecta deoarece nu vor exista {$j1$}, $j2$ cu $A{~j1~}$ si $A{~j2~}$ minim , iar {$V{~j1~} = V{~j2~}$}.
Problema se poate rezolva mai bine intr-o complexitate $O(N*lg^2^ N)$ folosind structuri de date avansate, astfel transformandu-se intr-o problema de clasele 11-12 grea, sau chiar o problema de finala. Lasam aceasta rezolvare ca exercitiu pentru cititor.

 
 
h2. Sum
 
h3. (problema usoara, clasa a 10a)
 
Vom face o prima observatie:
 
* $(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{~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.
 
h2. Pavare 2
 
h3. (problema grea, clasa a 10a)
 
Problema se rezolva cu programare dinamica. Utilizam urmatoare structura de date:
 
* $V[i][j]&#0091;0]$ = numarul de posibilitati pentru a pava $i$ metri astfel incat primele $j$ placi sa fie albe
* $V[i][j]&#0091;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]&#0091;0]$ (pentru {$1 &le; i &le; A$}) si $V[N][i]&#0091;1]$ pentru ({$1 &le; i &le; B$}).
 
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".