Problema mister — OJI 2026, Clasa X, rezolvare explicată

Algoritmul, pas cu pas

Ce face algoritmul. E deque-ul monoton de la maximul pe fereastră glisantă de lățime $K$ : $T[x..y]$ ține valori descrescătoare (candidați la maxim), iar $B_i$ e dimensiunea lui după pasul $i$ .

Reconstrucția. La pasul $i$ , dimensiunea se schimbă: $B_i = B_{i-1} + 1 - p - f$ , unde $p$ = scoateri din spate (le controlez prin valoarea aleasă) și $f \in \{0, 1\}$ = scoaterea din față (se întâmplă dacă fruntea e exact elementul care iese din fereastra de lățime $K$ ). Deci $p + f = B_{i-1} + 1 - B_i$ .

Dacă scoaterea din față e forțată (fruntea e elementul de la poziția $i-K$ ), atunci $f = 1$ și aleg $p = (B_{i-1}+1-B_i) - 1$ .
Altfel $f = 0$ și $p = B_{i-1}+1-B_i$ .

Alegerea valorilor. Am nevoie de o valoare care: scoate exact $p$ din spate (deci e mai mare decât cele $p$ cele mai mici, dar mai mică decât următoarea) — sau e mai mare decât tot (scoate tot), sau mai mică decât spatele (nu scoate nimic). Ca să am mereu „loc” între valori, lucrez cu o listă ordonată (dublu înlănțuită): inserez noul element fix sub elementul care rămâne în spate, sus de tot (scoatere totală), sau jos de tot (nicio scoatere). La final citesc rangurile $1..N$ din listă — ele dau $A$ .

Complexitate: $O(N)$ .

Soluția în C++

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

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

int main() {
    int N, K;
    fin >> N >> K;
    vector<int> B(N + 1);
    for (int i = 1; i <= N; i++) fin >> B[i];

    // listă ordonată: nodurile 0..N-1, plus HEAD (maxim) și TAIL (minim)
    int HEAD = N, TAIL = N + 1;
    vector<int> nxt(N + 2), prv(N + 2);
    nxt[HEAD] = TAIL; prv[TAIL] = HEAD;
    auto insertAfter = [&](int pos, int node) { // node devine imediat sub pos
        int b = nxt[pos];
        nxt[pos] = node; prv[node] = pos; nxt[node] = b; prv[b] = node;
    };

    vector<int> dq(N + 2); // deque de id-uri de noduri
    int lo = 0, hi = -1;
    for (int i = 1; i <= N; i++) {
        int node = i - 1;
        int prev = hi - lo + 1;
        int need = prev + 1 - B[i];           // p + f
        bool forced = (i > K) && (hi >= lo) && (dq[lo] == i - K - 1);
        int p, f;
        if (forced) { p = need - 1; f = 1; }
        else { p = need; f = 0; }

        if (p == prev) {                       // scoate tot din spate
            hi = lo - 1;
            insertAfter(HEAD, node);           // cel mai mare
        } else {
            if (p == 0) insertAfter(prv[TAIL], node);        // cel mai mic
            else insertAfter(dq[hi - p], node);              // sub elementul rămas în spate
            hi -= p;
        }
        if (f == 1) lo++;                      // scoatere din față
        hi++; dq[hi] = node;                   // adăugare
    }

    // rangurile: de la HEAD spre TAIL, cel mai mare primește N
    vector<int> A(N);
    int cur = nxt[HEAD], rank = N;
    while (cur != TAIL) { A[cur] = rank--; cur = nxt[cur]; }
    for (int i = 0; i < N; i++) fout << A[i] << (i + 1 < N ? ' ' : '\n');
    return 0;
}

Greșeli frecvente

Nu recunoști deque-ul monoton — fără să vezi că $B_i$ e dimensiunea deque-ului de la maximul pe fereastră, reconstrucția pare imposibilă.
Greșești când scoaterea din față e forțată — dacă fruntea e exact elementul care iese din fereastră, $f=1$ obligatoriu; trebuie să scazi unul din scoaterile din spate, altfel dimensiunea nu iese $B_i$ .
Încerci să alegi valori întregi „între” direct — nu mereu există loc; folosește o listă ordonată și abia la final atribuie rangurile $1..N$ .

Algoritmul, pas cu pas

Ce face algoritmul. E deque-ul monoton de la maximul pe fereastră glisantă de lățime

K

T[x..y]

ține valori descrescătoare (candidați la maxim), iar

B_i

e dimensiunea lui după pasul

i

Reconstrucția. La pasul

i

, dimensiunea se schimbă:

B_i = B_{i-1} + 1 - p - f

, unde

p

= scoateri din spate (le controlez prin valoarea aleasă) și

f \in \{0, 1\}

= scoaterea din față (se întâmplă dacă fruntea e exact elementul care iese din fereastra de lățime

K

). Deci

p + f = B_{i-1} + 1 - B_i

Dacă scoaterea din față e forțată (fruntea e elementul de la poziția

i-K

), atunci

f = 1

și aleg

p = (B_{i-1}+1-B_i) - 1

Altfel

f = 0

și

p = B_{i-1}+1-B_i

Alegerea valorilor. Am nevoie de o valoare care: scoate exact

p

din spate (deci e mai mare decât cele

p

cele mai mici, dar mai mică decât următoarea) — sau e mai mare decât tot (scoate tot), sau mai mică decât spatele (nu scoate nimic). Ca să am mereu „loc” între valori, lucrez cu o listă ordonată (dublu înlănțuită): inserez noul element fix sub elementul care rămâne în spate, sus de tot (scoatere totală), sau jos de tot (nicio scoatere). La final citesc rangurile

1..N

din listă — ele dau

A

Complexitate:

O(N)

Soluția în C++

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

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

int main() {
    int N, K;
    fin >> N >> K;
    vector<int> B(N + 1);
    for (int i = 1; i <= N; i++) fin >> B[i];

    // listă ordonată: nodurile 0..N-1, plus HEAD (maxim) și TAIL (minim)
    int HEAD = N, TAIL = N + 1;
    vector<int> nxt(N + 2), prv(N + 2);
    nxt[HEAD] = TAIL; prv[TAIL] = HEAD;
    auto insertAfter = [&](int pos, int node) { // node devine imediat sub pos
        int b = nxt[pos];
        nxt[pos] = node; prv[node] = pos; nxt[node] = b; prv[b] = node;
    };

    vector<int> dq(N + 2); // deque de id-uri de noduri
    int lo = 0, hi = -1;
    for (int i = 1; i <= N; i++) {
        int node = i - 1;
        int prev = hi - lo + 1;
        int need = prev + 1 - B[i];           // p + f
        bool forced = (i > K) && (hi >= lo) && (dq[lo] == i - K - 1);
        int p, f;
        if (forced) { p = need - 1; f = 1; }
        else { p = need; f = 0; }

        if (p == prev) {                       // scoate tot din spate
            hi = lo - 1;
            insertAfter(HEAD, node);           // cel mai mare
        } else {
            if (p == 0) insertAfter(prv[TAIL], node);        // cel mai mic
            else insertAfter(dq[hi - p], node);              // sub elementul rămas în spate
            hi -= p;
        }
        if (f == 1) lo++;                      // scoatere din față
        hi++; dq[hi] = node;                   // adăugare
    }

    // rangurile: de la HEAD spre TAIL, cel mai mare primește N
    vector<int> A(N);
    int cur = nxt[HEAD], rank = N;
    while (cur != TAIL) { A[cur] = rank--; cur = nxt[cur]; }
    for (int i = 0; i < N; i++) fout << A[i] << (i + 1 < N ? ' ' : '\n');
    return 0;
}

Greșeli frecvente

Nu recunoști deque-ul monoton — fără să vezi că $B_i$ e dimensiunea deque-ului de la maximul pe fereastră, reconstrucția pare imposibilă.
Greșești când scoaterea din față e forțată — dacă fruntea e exact elementul care iese din fereastră, $f=1$ obligatoriu; trebuie să scazi unul din scoaterile din spate, altfel dimensiunea nu iese $B_i$ .
Încerci să alegi valori întregi „între” direct — nu mereu există loc; folosește o listă ordonată și abia la final atribuie rangurile $1..N$ .

mister

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++

mister

Ce cere problema?

Indicii

Algoritmul, pas cu pas

Soluția în C++