Problema A - Salvando os Ruivacos

O Problema

Dados inteiros $N$, $K$, $T$ e uma sequência de $N$ inteiros, calcular o número de subsequências contíguas de comprimento $K$ em que pelo menos metade dos elementos são menores ou iguais a $T$.

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

Os casos de teste deste problema estão organizados em 2 grupos com restrições adicionais diferentes:

Solução Base

A solução mais imediata é pensar em todos os intervalos possíveis de $K$ elementos de entre $N$ inteiros e depois analisar cada intervalo de forma independente. Sendo $[i, i+K-1]$ o intervalo que inclui os inteiros na posição $i$, $i+K-1$ e todos os restantes inteiros entre eles, serão analisados todos os intervalos da forma $[i, i+K-1]$, para $i$ entre $0$ e $N-K$ inclusive. Para cada um destes intervalos, determinarmos se cumpre com a condição exigida no enunciado, iterando sobre todos os elementos em $[i,i+K-1]$ e contando quantos elementos são maiores ou iguais a $T$. Depois, se esse número for pelo menos metade de $K$, então esse intervalo tem pelo menos metade dos seus elementos maiores que $T$, logo é mais um intervalo a considerar para a resposta. Para determinarmos de um número $X$ é maior ou igual a metade de $K$ podemos ver se $2X \geq K$ e assim evitamos ter que usar números não inteiros.

Esta solução pode ser implementada através do seguinte pedaço de código:

#include <stdio.h>

int seq[100000];

int main() {
  int n, k, t;
  scanf("%d %d %d", &n, &k, &t);

  for (int i = 0; i < n; i++)
    scanf("%d", &seq[i]);

  int resultado = 0;
  for (int i = 0; i+k <= n; i++){
    int contador = 0;

    for (int j = i; j < i+k; j++)
      if (seq[j] >= t)
        contador++;

    if (2 * contador >= k)
      resultado++;
  }

  printf("%d\n", resultado);
  return 0;
}

Vamos agora fazer a análise da complexidade temporal deste algoritmo. Se ainda não leste o conjunto de artigos de iniciação às ONI é muito importante que o faças. Entre outros temas mais introdutórios e avançados abordamos como analisar um programa de modo a conseguir estimar quantos pontos terá. Vamos fazer essa análise a seguir para o código acima a seguir.

Artigo: Guia de iniciação às ONI

No 4o artigo deste guia abordamos o tema de análise de complexidade.

Existem no total $N-K+1$ sub-intervalos de $K$ elementos em $N$ elementos. Para cada intervalo, iteramos sobre cada um dos seus $K$ elementos. Assim, realizamos exatamente $(N+1-K)K = (N+1)K-K^2 $ operações. Para um determinado valor de $N$, o valor da expressão anterior é máximo para $K=(N+1)/2$, que substituindo dá-nos o máximo de $(N+1)^2/2-(N+1)^2/4 = (N+1)^2/4$. Em notação Big-O, a complexidade desta solução é traduzida por $O(N^2)$, que executa sem problema para o Grupo 1 dentro do limite de tempo de 1 segundo, mas ultrapassa este limite de tempo para soluções com $N$ aproximadamente maior que $10 000$, arrecadando assim um máximo de 40 pontos.

Solução Ótima

A solução ótima passa por reutilizar o resultado relativo ao intervalo anterior para inferir sobre a constituição do intervalo atual, implementando um conceito conhecido como "sliding window". Este conceito sugere que o problema de analisar vários subintervalos seja encarado como um problema em que existe uma "janela" que desliza ao longo dos dados, de forma a facilitar a compreensão do que muda quando se "desliza a janela" numa das direções, sendo que a mudança se encontra associada aos extremos da janela, uma vez que a maior parte dos elementos permanecem dentro da janela quando esta é movida uma unidade para um dos lados.

Assim, imaginem que temos uma variável $X$ que contém o número elementos do intervalo $[i, i+K-1]$ são maiores ou iguais a $T$. Podemos rapidamente determinar quantos elementos de $[i+1, i+K]$ são maiores que $T$, uma vez que:

• Os elementos $[i+1, i+K-1]$ são comuns aos intervalos $[i, i+K-1]$ e $[i+1, i+K]$.
• Os únicos elementos que diferem entre os dois intervalos são $i$ e $i+K$.

Se analisarmos o elemento $i$ e determinarmos que é maior ou igual a $T$, então quando passamos para $[i+1, i+K]$ esse elemento desaparece, logo temos menos um elemento maior ou igual a $T$ na nossa janela, o que corresponde a decrementar $X$. Além disso, o elemento $i+K$ faz parte do novo intervalo, logo se esse elemento for maior ou igual a $T$, temos mais um elemento maior ou igual a $T$, o que corresponde a incrementar $X$.

Assim, a solução segue os seguintes passos:

1. Mantemos uma variável contador $A$ que representará a resposta
2. Determinamos o valor inicial de $X$, que corresponde ao número de elementos no intervalo $[0, K-1]$ que são maiores ou iguais a $T$, iterando sobre esses elementos e comparando-os com $T$. Esse valor de $X$ é comparado com $K$, e se for maior ou igual que sua metade (podemos usar o mesmo "truque" que usámos para a solução anterior) incrementamos $A$.
3. A partir do valor de $X$ para o intervalo inicial ($[0, K-1]$), determinamos o número de elementos maiores ou iguais que $T$ para o próximo intervalo ($[1, K]$), usando as regras definidas anteriormente, e atualizamos o valor de $X$ de acordo com isso.
4. Comparamos o valor de $X$ com $K$, e se for maior ou igual que sua metade incrementamos $A$.
5. Repetimos o passo anterior até passar por todos os intervalos.

Esta solução pode ser implementada através do seguinte pedaço de código:

#include <stdio.h>

int seq[100000];

int main() {
  int n, k, t;
  scanf("%d %d %d", &n, &k, &t);

  for (int i = 0; i < n; i++)
    scanf("%d", &seq[i]);

  int resultado = 0;
  int X = 0;
  for (int j = 0; j < k; j++)
    if (seq[j] >= t)
      X++;

  if (2 * X >= k)
    resultado++;

  for (int j = k; j < n; j++) {
    if (seq[j - k] >= t)
      X--;

    if (seq[j] >= t)
      X++;


    if (2 * X >= k)
      resultado++;
  }

  printf("%d\n", resultado);
  return 0;
}

No passo 2. são realizadas $K$ operações, e nos restantes passos apenas uma. Repetimos os passos 3. e 4. $N - K$ vezes, logo no total fazemos apenas $N$ operações, o que implica uma complexidade temporal $O(N)$, que arrecada a totalidade dos 100 pontos.