Problema se rezolva prin metoda programarii dinamice. Conditia din enunt se poate enunta astfel: elementul $a{~i~}$ dintr-un p-sir trebuie sa fie inclus strict in intervalul determinat de $a{~i-1~}$ si $a{~i-2~}$. Vom calcula $Nr[i][j]$ numarul de p-subsiruri care au ultimiii doi termeni $P{~i~}$ si $P{~j~} (i < j)$.
Vom presupune ca $P{~i~} < P{~j~}$, cazul $P{~i~} > P{~j~}$ putand fi tratat asemanator. $Nr[i][j]$ se va calcula ca suma de $Nr[k][i]$ cu proprietatea $P{~i~} < P{~j~} < P{~k~}$. O implementare directa a acestei rezolvari are complexitatea $O(N^3^)$ si ar fi obtinut $30$ de puncte. Daca sortam vectorul $P$ dat la intrare, valorile $k < i$ care respecta conditia $P{~j~} < P{~k~}$ vor forma un interval continuu ca indici. Vom calcula sume partiale pentru coloana $i$ din matricea $Nr$ parcurgand liniile matricii in ordinea sortarii. Astfel, calculul lui $Nr[i][j]$ se reduce la scaderea a doua sume partiale. Pentru a identifica exact ce sume se scad se poate folosi o cautare binara, reducand astfel rezolvarea la $O(N^2^*lg N)$.
Mentionam ca se poate obtine si o solutie $O(N^2^)$ daca se calculeaza valorile de pe linia $i$ din matricea $Nr$ in ordinea sortarii. Putem astfel renunta la cautare binara, deoarece indicele in care se face scaderea sumelor partiale va fi monoton.

Ca o ultima precizare, nu era necesar folosirea tipurilor de date pe $64$ de biti pentru a efectua operatii modulo $2^32^$. Mai mult, nu este necesar nici macar folosirea operatiei modulo. Daca se foloseste un tip intreg pe $32$ fara semn ($unsigned$ in $C/C++$) orice operatie cu variabile de acest tip este automat modulo $2^32^$.

Ca o ultima precizare, nu era necesar folosirea tipurilor de date pe $64$ de biti pentru a efectua operatii modulo $2^32^$. Mai mult, nu este necesar nici macar folosirea operatiei modulo. Daca se foloseste un tip intreg pe $32$ fara semn ($unsigned$ in $C/C++$) orice operatie cu variabile de acest tip este automat modulo $2^32^.

h2. 'Eval':problema/eval