Solutii

Maxsecv

(clasele 9-10)

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.

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)

Vom construi o procedura cu ajutorul careia vom numara cate secvente exista care contin cel mult X elemente distincte. Folosind aceasta procedura, rezultatul problemei va fi: numarul de secvente cu cel mult U elemente distincte - numarul de secvente cu cel mult L-1 elemente distincte.
La primul pas, vom normaliza valorile din sirul de intrare, inlocuind fiecare valoare cu un numar de la 1 la N (spre exemplu sirul 13 13 47 9 9 devine 1 1 2 3 3). Aceasta normalizare se poate face in O(N*lg N) cu o sortare, dar aceasta solutie va obtine doar 80 de puncte. Pentru 100 de puncte normalizarea trebuie facuta folosind o tabela hash.
Fie L_i cel mai mic indice astfel incat secventa cu elementele L_i...i contine cel mult X elemente distincte (cu alte cuvinte cea mai lunga secventa cu maxim X elemente distincte care se termina pe pozitia i). Numarul total de subsecvente va fi (1-L₁+1) + (2-L₂+1) + (3-L₃+1) + ... + (N-L_N+1).
Este usor de aratat ca L_i ≤ L_i+1 pentru orice i. Asadar, pe masura ce trecem de la i la i+1 vom incepe calculul lui L_i+1 de la valoarea L_i. Pentru a stii la fiecare moment cate elemente distincte sunt in secventa L_i...i vom mentine un vector V cu proprietatea ca V[x] = de cate ori apare x in secventa si o variabila Nr reprezentand numarul de valori distincte din secventa. Valorea lui Nr va creste doar cand V[x] se schimba din 0 in 1, si va scade doar cand V[x] se schimba din 1 in 0 (pentru un x oarecare). Complexitatea totala a algoritmului este O(N).