Numărarea secvențelor — câte secvențe respectă o proprietate

De ce contează?

La un magazin vrei să afli în câte intervale de zile consecutive ai cheltuit cel mult 100 de lei. Nu te interesează care anume, ci câte sunt. Numărarea secvențelor e exact asta: nu le afișezi, le numeri — repede.

Câte secvențe există?

O secvență (subsecvență contiguă) e dată de un capăt stânga și unul dreapta. Un vector cu n elemente are

1 + 2 + ... + n = n(n+1)/2

secvențe în total. Pentru n = 1000 sunt ~500.000 — prea multe ca să le verifici pe fiecare în detaliu dacă faci muncă suplimentară pe fiecare.

Observația-cheie

Trucul numărării: nu enumera secvențele una câte una. Pentru fiecare capăt drept dr, numără dintr-o singură mișcare câte începuturi st dau o secvență validă.

Exemplu: secvențe cu sumă ≤ S

Numărăm câte secvențe contigue au suma ≤ S (elemente pozitive). Folosim aceeași fereastră variabilă din lecția precedentă, dar acum numărăm, nu măsurăm lungimea.

Cheia: dacă [st, dr] e cea mai lungă secvență validă care se termină în dr, atunci toate secvențele care se termină în dr și încep la st, st+1, ..., dr sunt valide. Sunt dr - st + 1 la număr.

Pas cu pas pe numere

Fie v = {1, 2, 1, 3} și S = 3.

v	1	2	1	3
	1	2	3	4
	st	dr

dr=2: cea mai lungă validă e [1,2] sumă=3 → 2 secvențe noi: {2}, {1,2}.

Numărăm pe rând, pentru fiecare dr:

dr=1: fereastra [1,1] suma=1<=3 -> st=1 -> 1-1+1 = 1 secventa
dr=2: fereastra [1,2] suma=3<=3 -> st=1 -> 2-1+1 = 2 secvente
dr=3: suma=4>3 -> st=2; [2,3] suma=3 -> 3-2+1 = 2 secvente
dr=4: suma=1+3=4>3 -> st=3; [3,4]? suma=1+3=4>3 -> st=4; [4,4] suma=3 -> 1
total: 1 + 2 + 2 + 1 = 6 secvente cu suma <= 3

Cele 6 secvențe sunt: {1}, {2}, {1,2}, {1}, {3} și {1} (a treia poziție) — toate cu sumă ≤ 3.

Implementare C++

#include <iostream>
using namespace std;

int main() {
    int v[] = {0, 1, 2, 1, 3}; // v[0] nefolosit
    int n = 4, S = 3;

    int st = 1, suma = 0;
    long long total = 0; // poate fi mare: pana la n(n+1)/2
    for (int dr = 1; dr <= n; dr++) {
        suma += v[dr];
        while (suma > S) {       // strangem pana redevine valida
            suma -= v[st];
            st++;
        }
        total += dr - st + 1;    // cate secvente valide se termina in dr
    }

    cout << total << "\n"; // 6
    return 0;
}

Complexitate

Metodă	Timp	Spațiu
Verifici toate secvențele	O(n²) sau O(n³)	O(1)
Numărare cu doi indici	O(n)	O(1)

Vizualizare

Urmărește cum fereastra [st, dr] se lărgește la dreapta și se strânge la stânga când suma depășește S, iar la fiecare pas adaugi dr − st + 1 secvențe valide la total:

Greșeli frecvente

Greșeli frecvente de concurs:

Overflow la total. Numărul de secvențe poate ajunge la n(n+1)/2, adică ~5·10^11 pentru n = 10^6. Folosește long long, nu int.
Numeri secvențe greșite. Pentru fiecare dr aduni dr - st + 1, nu 1. Fiecare început valid contează separat.
Aplici metoda pe valori negative. Numărarea cu fereastră merge doar dacă proprietatea e monotonă (sume cu elemente pozitive). Cu negative, o secvență mai scurtă nu e neapărat „mai validă”.
Confuzi secvență cu submulțime. Aici numeri elemente consecutive. Submulțimile (elemente oarecare) sunt 2ⁿ — cu totul altă problemă.

Ilustrație

Pentru dr fixat, toate începuturile de la st la dr dau secvențe valide:

v	1	2	1	3
	1	2	3	4

dr=3, st=2: secvențele {2,1} și {1} sunt valide → 2 secvențe.

Recapitulare

Un vector are n(n+1)/2 secvențe contigue — prea multe pentru verificare individuală.
Pentru fiecare capăt dr, numeri dintr-un foc câte începuturi valide există: dr - st + 1.
Total O(n); atenție la overflow pe total (folosește long long).