Problema cibernetica — OJI 2026, Clasa IX, rezolvare explicată

Algoritmul, pas cu pas

Sunt $\frac{N(N+1)}{2}$ ferestre (până la $\sim 5 \cdot 10^{11}$ ) — nu le pot enumera. Salvarea: ambele proprietăți sunt monotone în lungime — dacă $[i, j]$ e validă, atunci și $[i, j+1]$ e validă (mai multe elemente nu scad nici frecvența maximă, nici numărul de distincte).

Deci, pentru fiecare start $i$ , există un capăt drept minim $r(i)$ de la care fereastra devine validă; toate ferestrele $[i, r(i)], [i, r(i)+1], \dots, [i, N]$ sunt valide — adică $N - r(i) + 1$ ferestre. Și $r(i)$ nu scade când $i$ crește, deci folosesc doi pointeri.

Cerința 2 (legitime, $\ge K$ distincte). Țin numărul de adrese distincte din fereastra curentă (cu un vector de frecvențe). Pentru fiecare $i$ extind dreapta până am $K$ distincte, adaug $N - r + 1$ , apoi scot $a_i$ .

Cerința 1 (suspecte, o adresă de $\ge K$ ori). Țin numărul de valori care au atins frecvența $K$ în fereastră; fereastra e suspectă cât timp acel contor e pozitiv. Aceeași glisare.

Complexitate: $O(N)$ (fiecare pointer parcurge șirul o singură dată), cu un vector de frecvențe de dimensiune $\max a_i$ .

Soluția în C++

#include <fstream>
#include <vector>
using namespace std;

ifstream fin("cibernetica.in");
ofstream fout("cibernetica.out");

int main() {
    int C;
    long long N, K;
    fin >> C >> N >> K;
    vector<int> a(N);
    int mx = 0;
    for (auto &x : a) { fin >> x; if (x > mx) mx = x; }
    vector<int> freq(mx + 1, 0);
    long long total = 0;

    if (C == 2) { // ferestre legitime: >= K adrese distincte
        int distinct = 0, r = 0;
        for (int i = 0; i < N; i++) {
            while (r < N && distinct < K) {
                if (freq[a[r]] == 0) distinct++;
                freq[a[r]]++;
                r++;
            }
            if (distinct >= K) total += N - r + 1;
            if (freq[a[i]] == 1) distinct--;
            freq[a[i]]--;
        }
    } else { // C == 1: ferestre suspecte: o adresă cu frecvență >= K
        int numK = 0, r = 0; // câte valori au atins frecvența K
        for (int i = 0; i < N; i++) {
            while (r < N && numK == 0) {
                freq[a[r]]++;
                if (freq[a[r]] == K) numK++;
                r++;
            }
            if (numK > 0) total += N - r + 1;
            if (freq[a[i]] == K) numK--;
            freq[a[i]]--;
        }
    }
    fout << total << "\n";
    return 0;
}

Greșeli frecvente

Enumerezi toate ferestrele — $O(N^2)$ înseamnă $\sim 10^{12}$ operații; folosește monotonia și doi pointeri pentru $O(N)$ .
Folosești int pentru rezultat — numărul de ferestre poate ajunge la $\sim 5 \cdot 10^{11}$ , deci long long.
Uiți să scoți $a_i$ din fereastră când treci la următorul start — altfel frecvențele și numărul de distincte rămân greșite.

Algoritmul, pas cu pas

Sunt

\frac{N(N+1)}{2}

ferestre (până la

\sim 5 \cdot 10^{11}

) — nu le pot enumera. Salvarea: ambele proprietăți sunt monotone în lungime — dacă

[i, j]

e validă, atunci și

[i, j+1]

e validă (mai multe elemente nu scad nici frecvența maximă, nici numărul de distincte).

Deci, pentru fiecare start

i

, există un capăt drept minim

r(i)

de la care fereastra devine validă; toate ferestrele

[i, r(i)], [i, r(i)+1], \dots, [i, N]

sunt valide — adică

N - r(i) + 1

ferestre. Și

r(i)

nu scade când

i

crește, deci folosesc doi pointeri.

Cerința 2 (legitime, $\ge K$ distincte). Țin numărul de adrese distincte din fereastra curentă (cu un vector de frecvențe). Pentru fiecare

i

extind dreapta până am

K

distincte, adaug

N - r + 1

, apoi scot

a_i

Cerința 1 (suspecte, o adresă de $\ge K$ ori). Țin numărul de valori care au atins frecvența

K

în fereastră; fereastra e suspectă cât timp acel contor e pozitiv. Aceeași glisare.

Complexitate:

O(N)

(fiecare pointer parcurge șirul o singură dată), cu un vector de frecvențe de dimensiune

\max a_i

Soluția în C++

#include <fstream>
#include <vector>
using namespace std;

ifstream fin("cibernetica.in");
ofstream fout("cibernetica.out");

int main() {
    int C;
    long long N, K;
    fin >> C >> N >> K;
    vector<int> a(N);
    int mx = 0;
    for (auto &x : a) { fin >> x; if (x > mx) mx = x; }
    vector<int> freq(mx + 1, 0);
    long long total = 0;

    if (C == 2) { // ferestre legitime: >= K adrese distincte
        int distinct = 0, r = 0;
        for (int i = 0; i < N; i++) {
            while (r < N && distinct < K) {
                if (freq[a[r]] == 0) distinct++;
                freq[a[r]]++;
                r++;
            }
            if (distinct >= K) total += N - r + 1;
            if (freq[a[i]] == 1) distinct--;
            freq[a[i]]--;
        }
    } else { // C == 1: ferestre suspecte: o adresă cu frecvență >= K
        int numK = 0, r = 0; // câte valori au atins frecvența K
        for (int i = 0; i < N; i++) {
            while (r < N && numK == 0) {
                freq[a[r]]++;
                if (freq[a[r]] == K) numK++;
                r++;
            }
            if (numK > 0) total += N - r + 1;
            if (freq[a[i]] == K) numK--;
            freq[a[i]]--;
        }
    }
    fout << total << "\n";
    return 0;
}

Greșeli frecvente

Enumerezi toate ferestrele — $O(N^2)$ înseamnă $\sim 10^{12}$ operații; folosește monotonia și doi pointeri pentru $O(N)$ .
Folosești int pentru rezultat — numărul de ferestre poate ajunge la $\sim 5 \cdot 10^{11}$ , deci long long.
Uiți să scoți $a_i$ din fereastră când treci la următorul start — altfel frecvențele și numărul de distincte rămân greșite.

cibernetica

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

cibernetica

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++