Problema pisicesc — OJI 2026, Clasa VIII, rezolvare explicată

Algoritmul, pas cu pas

Cerința 1. Marchez ce vocale apar (un vector de $5$ bool) și le număr.

Cerința 2. Glisez o fereastră de $3$ litere și număr unde se potrivește cu mau.

Cerința 3 — secvența-mesaj.

Observația cheie: o secvență de lungime $L$ apare de cel mult atâtea ori cât prefixul ei de $2$ litere. Deci frecvența maximă $F$ peste toate secvențele se atinge deja la lungime 2.
Calculez $F$ = frecvența maximă a secvențelor de lungime $2$ .
Frecvența maximă scade (nu crește) când mărim lungimea. Cresc $L$ de la $2$ în sus cât timp frecvența maximă la lungimea $L$ rămâne egală cu $F$ ; ultima astfel de lungime e $L_{best}$ .
Dintre secvențele de lungime $L_{best}$ care apar exact de $F$ ori, o aleg pe cea minim lexicografic.

Pentru a număra rapid aparițiile tuturor secvențelor de o lungime dată folosesc hashing polinomial (rolling hash), în $O(n)$ pe lungime. Complexitate totală: $O(n^2)$ în cel mai rău caz (suficient pentru $n \le 2000$ ).

Soluția în C++

#include <fstream>
#include <string>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;

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

int n;
string s;

// frecvența maximă a secvențelor de lungime L (rolling hash, modulo 2^64)
long long maxCountAt(int L) {
    unordered_map<ull, int> mp;
    ull base = 131, pw = 1, h = 0;
    for (int i = 0; i < L; i++) { h = h * base + (ull)s[i]; if (i) pw *= base; }
    long long best = ++mp[h];
    for (int i = L; i < n; i++) {
        h = (h - (ull)s[i - L] * pw) * base + (ull)s[i];
        int c = ++mp[h];
        if (c > best) best = c;
    }
    return best;
}

int main() {
    int C;
    fin >> C >> s;
    n = (int)s.size();

    if (C == 1) {
        bool seen[5] = {false};
        string vow = "aeiou";
        int cnt = 0;
        for (char c : s) {
            size_t p = vow.find(c);
            if (p != string::npos && !seen[p]) { seen[p] = true; cnt++; }
        }
        fout << cnt << "\n";
    } else if (C == 2) {
        int cnt = 0;
        for (int i = 0; i + 3 <= n; i++)
            if (s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'u') cnt++;
        fout << cnt << "\n";
    } else { // C == 3
        long long F = maxCountAt(2);
        int Lbest = 2;
        for (int L = 3; L <= n; L++) {
            if (maxCountAt(L) == F) Lbest = L;
            else break; // frecvența maximă a scăzut sub F
        }
        // lex-min dintre secvențele de lungime Lbest cu exact F apariții
        unordered_map<ull, int> cnt;
        unordered_map<ull, int> primaPoz;
        ull base = 131, pw = 1, h = 0;
        for (int i = 0; i < Lbest; i++) { h = h * base + (ull)s[i]; if (i) pw *= base; }
        cnt[h]++; primaPoz[h] = 0;
        for (int i = Lbest; i < n; i++) {
            h = (h - (ull)s[i - Lbest] * pw) * base + (ull)s[i];
            cnt[h]++;
            if (!primaPoz.count(h)) primaPoz[h] = i - Lbest + 1;
        }
        string ans = "";
        for (auto &kv : cnt)
            if (kv.second == F) {
                string cand = s.substr(primaPoz[kv.first], Lbest);
                if (ans == "" || cand < ans) ans = cand;
            }
        fout << ans << "\n";
    }
    return 0;
}

Greșeli frecvente

Cauți frecvența maximă pe toate lungimile fără observația-cheie — risipești timp; frecvența maximă se atinge la lungime $2$ , restul e doar extinderea ei.
Uiți departajarea completă la cerința 3 — întâi număr maxim de apariții, apoi lungime maximă, apoi lexicografic; dacă sari peste „cea mai lungă”, întorci ma în loc de mam.
Compari toate secvențele ca șiruri întregi — pentru $n = 2000$ asta poate ajunge la $O(n^3)$ ; folosește hashing pentru numărare și compară ca șiruri doar candidații finali.

Algoritmul, pas cu pas

Cerința 1. Marchez ce vocale apar (un vector de

5

bool) și le număr.

Cerința 2. Glisez o fereastră de

3

litere și număr unde se potrivește cu mau.

Cerința 3 — secvența-mesaj.

Observația cheie: o secvență de lungime

L

apare de cel mult atâtea ori cât prefixul ei de

2

litere. Deci frecvența maximă

F

peste toate secvențele se atinge deja la lungime 2.

Calculez

F

= frecvența maximă a secvențelor de lungime

2

Frecvența maximă scade (nu crește) când mărim lungimea. Cresc

L

de la

2

în sus cât timp frecvența maximă la lungimea

L

rămâne egală cu

F

; ultima astfel de lungime e

L_{best}

Dintre secvențele de lungime

L_{best}

care apar exact de

F

ori, o aleg pe cea minim lexicografic.

Pentru a număra rapid aparițiile tuturor secvențelor de o lungime dată folosesc hashing polinomial (rolling hash), în

O(n)

pe lungime. Complexitate totală:

O(n^2)

în cel mai rău caz (suficient pentru

n \le 2000

Soluția în C++

#include <fstream>
#include <string>
#include <unordered_map>
using namespace std;
typedef unsigned long long ull;

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

int n;
string s;

// frecvența maximă a secvențelor de lungime L (rolling hash, modulo 2^64)
long long maxCountAt(int L) {
    unordered_map<ull, int> mp;
    ull base = 131, pw = 1, h = 0;
    for (int i = 0; i < L; i++) { h = h * base + (ull)s[i]; if (i) pw *= base; }
    long long best = ++mp[h];
    for (int i = L; i < n; i++) {
        h = (h - (ull)s[i - L] * pw) * base + (ull)s[i];
        int c = ++mp[h];
        if (c > best) best = c;
    }
    return best;
}

int main() {
    int C;
    fin >> C >> s;
    n = (int)s.size();

    if (C == 1) {
        bool seen[5] = {false};
        string vow = "aeiou";
        int cnt = 0;
        for (char c : s) {
            size_t p = vow.find(c);
            if (p != string::npos && !seen[p]) { seen[p] = true; cnt++; }
        }
        fout << cnt << "\n";
    } else if (C == 2) {
        int cnt = 0;
        for (int i = 0; i + 3 <= n; i++)
            if (s[i] == 'm' && s[i + 1] == 'a' && s[i + 2] == 'u') cnt++;
        fout << cnt << "\n";
    } else { // C == 3
        long long F = maxCountAt(2);
        int Lbest = 2;
        for (int L = 3; L <= n; L++) {
            if (maxCountAt(L) == F) Lbest = L;
            else break; // frecvența maximă a scăzut sub F
        }
        // lex-min dintre secvențele de lungime Lbest cu exact F apariții
        unordered_map<ull, int> cnt;
        unordered_map<ull, int> primaPoz;
        ull base = 131, pw = 1, h = 0;
        for (int i = 0; i < Lbest; i++) { h = h * base + (ull)s[i]; if (i) pw *= base; }
        cnt[h]++; primaPoz[h] = 0;
        for (int i = Lbest; i < n; i++) {
            h = (h - (ull)s[i - Lbest] * pw) * base + (ull)s[i];
            cnt[h]++;
            if (!primaPoz.count(h)) primaPoz[h] = i - Lbest + 1;
        }
        string ans = "";
        for (auto &kv : cnt)
            if (kv.second == F) {
                string cand = s.substr(primaPoz[kv.first], Lbest);
                if (ans == "" || cand < ans) ans = cand;
            }
        fout << ans << "\n";
    }
    return 0;
}

Greșeli frecvente

Cauți frecvența maximă pe toate lungimile fără observația-cheie — risipești timp; frecvența maximă se atinge la lungime $2$ , restul e doar extinderea ei.
Uiți departajarea completă la cerința 3 — întâi număr maxim de apariții, apoi lungime maximă, apoi lexicografic; dacă sari peste „cea mai lungă”, întorci ma în loc de mam.
Compari toate secvențele ca șiruri întregi — pentru $n = 2000$ asta poate ajunge la $O(n^3)$ ; folosește hashing pentru numărare și compară ca șiruri doar candidații finali.

pisicesc

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

pisicesc

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++