Solutii

Maxsecv

Se observa ca secventa maxima de 1 care se poate obtine are lungimea egala cu suma primelor doua secvente maxime din vectorul original. Printr-o operatie descrisa se pot alatura cu usurinta cele doua secvente.
Pentru obtinerea unei solutii liniare e suficient sa parcurgem vectorul de la stanga la dreapta si sa updatam la fiecare pas lungimea secventei curente de 1. In momentul in care ajungem la capatul unei astfel de secvente facem un update pentru primul si al 2-lea maxim, dupa caz.

(clasele 9-10)

...

Chernel

(clasele 9-10)

Considerandu-se sirul a₁ a₂ ... a_N pentru un N fixat, se observa ca dupa N-1 transformari, acesta devine a₁ * C_N-1⁰ + a₂ * C_N-1¹ + a₃ * C_N-1² + ... + a_N * C_N-1^N-1 . De aici reiese ca elementele sirului initial a calor valoare nu influenteaza numarul caracteristic (numarul din ultimul sir obtinut modulo M) sunt cele ai caror coeficienti sunt multipli ai lui M. Astfel problema se reduce la numararea combinarilor de N-1 luate cate i (cu i intre 0 si N-1) care sunt multipli de M. Aceasta se realizeaza simplu "generand" combinarile respective: ne bazam pe recurenta C_N^k+1 = C_N^k * (n-k) / (k+1) si verificam cate dintre acestea sunt divizibile cu M. Problema este ca aceste valori vor deveni uriase destul de rapid, iar stocarea lor in memoria calculatorului este ineficienta. Din acest motiv nu se vor retine numerele propriu zise, ci doar exponentii factorilor primi ai lui M, (numarul maxim de factori primi ai lui fiind aproximat la O(ln ln M), si 9 pentru datele de test ale problemei) care se vor actualiza pentru fiecare combinare procesata.
Complexitatea finala a algoritmului devine astfel O(N * ln ln M).

Amenzi

(clasele 11-12)

Problema se poate rezolva folosind metoda programarii dinamice. Se construieste matricea A_t,i in care se retine valoarea totala a amenzilor ce poate fi data pana la momentul t astfel incat la momentul t sa fim in intersectia i. Pentru toate muchiile (j,i) de cost c vom compara A_t,i cu A_t-c,j alegand maximul dintre aceste valori. De fapt ar trebui inspectate toate valorile A_t-c,j A_t-c-1,j ... A_1,j A_0,j dar este clar ca maximul acestor valori se afla in A_t-c,j. Deasemenea trebuie considerat cazul cand politistul sta pe loc deci ne vom uita si la valoarea din A_t-1,i. Apoi politistul va da toate amenzile posibile la momentul respectiv in intersectia respectiva deci vom aduna respectiva suma la A_t,i.
Avand construita aceasta matrice se poate raspunde in O(1) la fiecare intrebare.
Complexitatea totala va fi O(Tmax * M) ca timp si O( Tmax * N ) ca memorie.

Secventa 5

(clasele 11-12)

...