Dane jest $n$-literowe słowo, w którym szukamy najkrótszego fragmentu spełniającego $r$ wymagań postaci „litera $b_i$ musi występować we fragmencie co najmniej $q_i$ razy”.

Mała liczba wymagań

W podzadaniu 3 mamy małą liczbę wymagań, co pozwala nam analizować je w pewnym sensie niezależnie. Dla danego wymagania $b,q$ oraz dowolnego początku fragmentu $i$ możemy wyznaczyć taki koniec fragmentu $ri[i]$, że $[i..ri[i]]$ jest najkrótszym fragmentem spełniającym wymaganie. Robimy to metodą gąsienicy: zachłannie powiększamy $ri[i]$, aż do znalezienia $q$-tego wystąpienia litery $b$. Następnie, przechodząc z $i$ do $i+1$, zmniejszamy licznik $q$, jeśli $i$-tą literą słowa było $b$.

Teraz najkrótszy fragment zaczynający się w $i$ i spełniający wszystkie wymagania kończy się w $\max ri[i]$ (gdzie sumujemy po wszystkich tablicach dla wymagań).

Poniższy kod rozwiązuje zadanie w czasie $O(nr)$:

const int N = 210000, infty = 1000000000;
int n,k,r,a[N];
int sol[N];

int main() {
  scanf("%d%d%d",&n,&k,&r);
  REP(i,n) scanf("%d",&a[i]);
  REP(i,n) sol[i] = 0;

  REP(i,r) {
    int b,q;
    scanf("%d%d",&b,&q);

    int ri=0, cnt = 0;
    REP(le,n) {
      while (ri < n && cnt < q) {
        if (a[ri] == b) ++cnt;
        ri++;
      }
      int best = cnt < q ? infty : ri-le;
      sol[le] = max(sol[le], best);
      if (a[le] == b) --cnt;
    }
  }
  int ans = *min_element(sol, sol+n);
  if (ans == infty) {
    printf("impossible\n");
  } else {
    printf("%d\n", ans);
  }
}

Pełne rozwiązanie

Można przyspieszyć poprzedni algorytm, jednocześnie rozpatrując wszystkie wymagania. Nadal będziemy używać metody gąsienicy, przy czym teraz dla każdego wymagania $i$ będziemy utrzymywać licznik liter $cnt[i]$. Ponadto będziemy mieli licznik $C$, zliczający spełnione wymagania.

W momencie, gdy licznik $cnt[i]$ zwiększamy do wartości $q_i$, to właśnie zaczynamy spełniać $i$-te wymaganie, zatem zwiększamy $C$ o 1. Gdy licznik $cnt[i]$ zmniejszamy z wartości $q_i$, to tracimy $i$-te wymaganie, więc zmniejszamy też licznik $C$.

Fragment jest dobry, jeśli $C=r$. Poniższa modyfikacja działa zatem w czasie $O(n+r)$:

const int N = 210000, infty = 1000000000;
int n,k,r,a[N],b[N],q[N],alf[N];
int sol[N],cnt[N],C;

int main() {
  scanf("%d%d%d",&n,&k,&r);
  REP(i,n) scanf("%d",&a[i]);
  REP(i,n) sol[i] = 0;

  REP(i,k) alf[i] = -1;
  REP(i,r) {
    scanf("%d%d",&b[i],&q[i]);
    alf[b[i]] = i;
  }

  int ri=0;
  REP(le,n) {
    while (ri < n && C < r) {
      int rule = alf[a[ri]];
      if (rule != -1) {
        if (++cnt[rule] == q[rule]) { ++C; }
      }
      ri++;
    }

    sol[le] = C == r ? ri-le : infty;

    int rule = alf[a[le]];
    if (rule != -1) {
      if (cnt[rule]-- == q[rule]) { --C; }
    }
  }