h3. (problema usoara clasa a IX-a, problema usoara clasa a X-a)

Exista solutii evidente $O(N * (A-B))$ si $O(N * K)$ care obtin punctaje partiale si asupra carora nu se va insista in acest articol. Solutia care obtine insa $100$ de puncte este $O(N)$ si nu este greu de gasit, bazandu-se pe cateva observatii. Sa notam cu $S{~i~}$ suma primelor $i$ numere din sir. Pentru ca subsecventa intre pozitiile $i$ si $j$ sa aiba suma elementelor divizibila cu $K$, atunci $S{~j~}-S{~i-1~}$ trebuie sa fie divizibil cu $K$, sau altfel spus, $S{~i-1~}$ si $S{~j~}$ sa aiba acelasi rest la impartirea cu $K$. Daca stim sa aflam raspunsul problemei pentru subsecvente de lungime maxim $L$ si minim {$1$}, aplicand de doua ori algoritmul pentru $B$ si pentru $A-1$ si scazand cele doua valori obtinute vom obtine numarul de subsecvente cu proprietatea ceruta intre $A$ si $B$ inclusiv. Pentru a afla raspunsul pentru lungimea maxim $L$ procedam astfel: introducem in lista $LISTA{~r~}$ alocata dinamic pozitiile $i$ pentru care $S{~i~}$ da restul $r$ la impartirea cu $K$, in ordine crescatoare. Pentru fiecare rest de la $0$ la $K-1$ parcurgem lista
corespunzatoarea, si, daca ne aflam pe un element cu valoarea $p2$ si elementul cel mai din stanga din lista curenta are valoarea $p1$ astfel incat $p2-p1 ≤ L$, atunci cand avansam in lista nu mai este necesar sa incepem iterarea listei de la inceput pentru aflarea valorii cea mai din stanga, fiind suficient sa reluam cautarea din dreptul valorii $p1$. Astfel complexitatea algoritmului pentru o lista este $O(LUNGIME)$, unde $LUNGIME$ este lungimea unei liste, deci complexitatea intregului algoritm va fi $O(N)$, pentru ca lungimea tuturor listelor este $N$.

Exista solutii evidente $O(N * (A-B))$ si $O(N * K)$ care obtin punctaje partiale si asupra carora nu se va insista in acest articol. Solutia care obtine insa $100$ de puncte este $O(N)$ si nu este greu de gasit, bazandu-se pe cateva observatii. Sa notam cu $S{~i~}$ suma primelor $i$ numere din sir. Pentru ca subsecventa intre pozitiile $i$ si $j$ sa aiba suma elementelor divizibila cu $K$, atunci $S{~j~}-S{~i-1~}$ trebuie sa fie divizibil cu $K$, sau altfel spus, $S{~i-1~}$ si $S{~j~}$ sa aiba acelasi rest la impartirea cu $K$. Daca stim sa aflam raspunsul problemei pentru subsecvente de lungime maxim $L$ si minim {$1$}, aplicand de doua ori algoritmul pentru $B$ si pentru $A-1$ si scazand cele doua valori obtinute vom obtine numarul de subsecvente cu proprietatea ceruta intre $A$ si $B$ inclusiv. Pentru a afla raspunsul pentru lungimea maxim $L$ procedam astfel: introducem in lista $LISTA{~r~}$ alocata dinamic pozitiile $i$ pentru care $S{~i~}$ da restul $r$ la impartirea cu $K$, in ordine crescatoare. Pentru fiecare rest de la $0$ la $K-1$ parcurgem lista corespunzatoarea, si, daca ne aflam pe un element cu valoarea $p2$ si elementul cel mai din stanga din lista curenta are valoarea $p1$ astfel incat $p2-p1 ≤ L$, atunci cand avansam in lista nu mai este necesar sa incepem iterarea listei de la inceput pentru aflarea valorii cea mai din stanga, fiind suficient sa reluam cautarea din dreptul valorii $p1$. Astfel complexitatea algoritmului pentru o lista este $O(LUNGIME)$, unde $LUNGIME$ este lungimea unei liste, deci complexitatea intregului algoritm va fi $O(N)$, pentru ca lungimea tuturor listelor este $N$.

O alta solutie de aceeasi complexitate dar mai rapida este urmatoarea: daca notam cu @v[r]@ de cate ori apare restul $r$ in numerele $S{~i-B~}...S{~i-A+1~}$ pentru pasul curent $i$, atunci la pasul $i+1$ este suficient sa decrementam $v[S{~i-B+1~}%K]$ si sa incrementam $v[S{~i-A+2~}%K]$. La fiecare pas $i$ vom aduna la solutia finala numarul $v[S{~i~}%K]$.
h2. Lupul Urias si Rau