Problema C - Rua das Flores

Parte I

Dada uma sequência de $N$ inteiros positivos, encontrar a soma do segmento contíguo de comprimento $K$ com a menor soma.

Restrições

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

Solução

O problema desta parte é muito semelhante a alguns problemas antigos das ONI (ver, por exemplo, o problema A da qualificação de 2016 ). A solução só precisa de uma observação: vamos supor que sabemos a soma dos elementos do segmento entre $i$ e $i + K - 1$ (vamos chamar a este valor $S$) e queremos saber a soma dos elementos no segmento seguinte, ou seja, o segmento entre $i + 1$ e $i + K$ (vamos chamar a este valor $S'$, como podemos fazê-lo eficientemente (ou seja, sem fazer um ciclo que recalcula a soma)? Podemos observar que, visto que os elementos entre $i + 1$ e $i + K - 1$ fazem parte de ambas as somas, podemos apenas somar um elmemento e subtrair um elemento, ou seja: $S' = S - S_i + S_{i + K}$ (recordem que $S_i$ representa o $i$-ésimo elemento da sequência). Esta fórmula permite-nos "avançar" pelos segmentos e obter a soma de cada um em $O(1)$, ou seja, só precisamos de determinar o mínimo de todas as somas.

Uma nota de implementação importante: dadas as magnitudes dos possíveis valores de $S_i$, é importante representar as somas com tipos de inteiros que permitam representar números até $2^{63}$, ou seja, usar long long int em C++ ou long em Java.

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

#include <stdio.h>

int S[100000];

int main() {
  int P;
  scanf("%d", &P);
  int N, K;
  scanf("%d %d", &N, &K);

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

  if (P == 1) {
    long long int soma = 0;
    // Primeiro obtemos a soma do primeiro segmento
    for (int i = 0; i < K; i++)
      soma += S[i];
    long long int resposta = soma;
    for (int i = 0; i < N - K; i++) {
      soma = soma - S[i] + S[i + K];
      resposta = min(resposta, soma);
    }
    printf("%lld\n", resposta);
  }
  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.

A nossa solução efetua apenas um ciclo de 0 a $N$ (partido em dois, um de 0 a $K$ e um de $K$ a $N$, como podemos ver no código), logo a solução é $O(N)$. Isto é suficiente para resolver ambas a única subtarefa da primeira parte e obtém assim os 25 pontos desta parte.

Parte II

Dada uma sequência de $N$ inteiros positivos, encontrar a soma do segmento contíguo com a $K$-ésima menor soma.

Restrições

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

Solução

À primeira vista este problema parece impossível, como é que conseguimos obter qualquer tipo de informação sobre o segmento com a $K$-ésima menor soma? Neste tipo de situações é comum usar a seguinte ideia: "inverter o problema". Isto é, vamos antes fazer a seguinte pergunta: dado um inteiro $T$, quantos segmentos têm soma no máximo $T$? Estamos a inverter o problema porque a resposta ao problema é o menor valor $T$ para o qual existem exatamente $K$ segmentos com soma no máximo $T$. Este facto não é muito complicado, mas pensem um pouco porque é que é verdade.

Agora surgem duas questões: primeiro, como calcular este valor $T$; segundo, como usar este valor para obter a resposta. Vamos responder à segunda pergunta primeiro, ou seja, vamos supor que temos um algoritmo eficiente que dado um valor $T$, nos diz quantos segmentos têm soma no máximo $T$, agora como resolvemos este problema?

Aplicar o algoritmo de segmentos de soma máxima $T$

Observem que esta propriedade é monótona, ou seja, se há $X$ segmentos com soma no máximo $T_1$, então para qualquer $T_2 \geq T_1$ há pelo menos $X$ segmentos com soma no máximo $T_2$. Isto parece indicar que podemos aplicar a ideia de pesquisa binária.

Artigo: Vídeo de introdução a pesquisa binária

Neste vídeo exploramos o conceito de pesquisa binária, nomeadamente como fazer "pesquisa binária na resposta", o conceito necessário para resolver este problema.

Vamos ver como aplicar pesquisa binária aqui. Vamos supor que fixamos um valor de $T$ qualquer e corremos o nosso algoritmo eficiente e verificamos que há $X$ segmentos com soma no máximo $T$.

• Se $X < K$, então o segmento com a $K$-ésima menor soma tem de ter soma estritamente maior que $T$.
• Se $X \geq K$, então o segmento com a $K$-ésima menor soma tem de ter soma menor ou igual a $T$.

Isto corresponde exatamente a pesquisa binária. Seja $S_{\max}$ o valor da soma de todos os elmentos na sequência. Então podemos começar por ver quantos segmentos têm soma no máximo $S_{\max} / 2$. Se esse número for menor que $K$, então sabemos que a resposta está entre $1 + S_{\max} / 2$ e $S_{\max}$. Caso contrário, a resposta estará entre 0 e $S_{\max} / 2$. E agora repetimos o mesmo procedimento até a janela de intervalos possíveis descrescer a apenas um elemento, esse será a resposta!

Calcular o número de segmentos de soma máxima $T$

Agora que sabemos para que serve, vamos finalmente ver como funciona o algoritmo eficiente mencionado. Novamente, dado um inteiro $T$, quantos segmentos têm soma no máximo $T$?

Como sempre, há várias formas de fazer isto, vamos apenas ver uma. Vamos calcular o seguinte: para cada índice $i$ da sequência, vamos determinar qual o maior comprimento $X_i$ tal que o segmento de elementos entre $i$ e $i + X_i$ tem soma menor ou igual a $T$ (se não existir nenhuma, ou seja, se $S_i > T$, então vamos fixar que $X_i = -1$). Isto permite-nos saber para cada $i$ quantos segmentos começam nesse índice e têm soma no máximo $T$, é exatamente $X_i + 1$ (mais um facto que não é muito difícil de ver, mas pensem um pouco porquê).

Para calcular estes valores de $X_i$, novamente há imensas abordagens! Vamos ver a mais eficiente, que usa uma ideia conhecida como sliding window. A ideia é muito parecida à ideia que vimos na Parte I deste problema e é baseada na seguinte observação. Vamos supor que sabemos $X_i$ assim como a soma de todos os elementos entre $i$ e $i + X_i$ (vamos chamar a esta soma de $P_i$) e queremos determinar $X_{i + 1}$. Ora, sabemos então que a soma de todos os elementos entre $i$ e $i + X_i$ são no máximo $T$, logo sabemos também que a soma de todos os elementos entre $i + 1$ e $i + X_{i + 1}$ também são no máximo $T$ (recordem que os elementos são sempre positivos)! Logo, $X_{i + 1}$ é pelo menos $X_i - 1$. Sabemos ainda que a soma entre todos os valores entre $i + 1$ e $i + X_i$ é $P_i - S_i$ (onde $P_i$ é a soma de todos os elementos entre $i$ e $i + X_i$).

Para terminar, vamos supor que o nosso algoritmo que cálcula $X_{i + 1}$ faz algo como iterar desde $i + 1$ para a frente, mantendo a soma dos elementos até à posição atual, ou seja, o que faz o seguinte código:

int Ximais1 = -1;
int somaParcial = 0;
while (somaParcial + S[i + Ximais1 + 1] <= T) {
  somaParcial += S[i + Ximais1 + 1];
  Ximais1++;
}

Então podemos simplesmente aplicar o mesmo código, mas usar iniciar Ximais1 a $X_i - 1$ e somaParcial a $P_i - S_i$.

Se fizermos isto para cada $i$ (por ordem), então este algoritmo tem uma complexidade temporal de $O(N)$. Porquê? Pensem um pouco no que representa $X_i$. Olhem para o segmento de $i$ a $i + X_i$ e verifiquem que à medida que vamos avançando com o valor de $i$, o extremo direito do intervalo também avança sempre. Ou seja, o número total de iterações do ciclo while acima (somado para todos os valores de $i$) é no máximo $N$. Este é um argumento delicado, por isso têm de pensar bem porque é que resulta!

Implementação

Antes de olharem para o código, é de notar que a solução tem várias pequenas nuances que fomos ignorando. Nomeadamente, garantir que os ciclos que fomos mencionando não se estendem para fora da sequência $S$ (causando um erro de execução por aceder a uma posição de memória inválida).

#include <stdio.h>

int N;
long long int K;
int S[100000];

long long int menorQueT(long long int T) {
  long long int X = 0;

  int Ximais1 = 0;
  int somaParcial = 0;
  for (int i = 0; i < N; i++) {
    Ximais1 = max(-1, Ximais1 - 1);
    if (i > 0)
      somaParcial -= S[i - 1];

    while (i + Ximais1 + 1 < N && somaParcial + S[i + Ximais1 + 1] <= T) {
      somaParcial += S[i + Ximais1 + 1];
      Ximais1++;
    }

    X += Ximais1 + 1;
  }  

  return X;
}

int main() {
  int P;
  scanf("%d", &P);
  scanf("%d %lld", &N, &K);

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

  if (P == 2) {
    long long int Smax = 0;
    for (int i = 0; i < N; i++)
      Smax += S[i];

    long long int lo = 0, hi = Smax;
    while (lo < hi) {
      long long int med = (lo + hi) / 2;

      if (menorQueT(med) < K) {
        lo = med + 1;
      }
      else {
        hi = med;
      }
    }

    printf("%lld\n", lo);
  }
  return 0;
}

Complexidade temporal

Nesta solução temos duas partes: uma pesquisa binária que tem um custo de $O(\log S_{\max})$ operações; uma sliding window que tem um custo de $O(N)$ operações. No total, o nosso algoritmo tem uma complexidade temporal de $O(N\log S_{\max})$. Isto é suficiente para resolver ambas as subtarefas da segunda parte e obtém assim os 50 pontos desta parte.

Parte III

Dada uma sequência de $N$ inteiros positivos, encontrar a soma do segmento contíguo com a $K$-ésima menor média (arredondada para baixo).

Restrições

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

Solução

A Parte III é muito semelhante à Parte II, mas infelizmente a solução da Parte II já não funciona. Pensem um pouco porque não funciona: como é que podemos calcular os $X_i$ eficientemente?

Ainda assim, vamos aplicar a mesma ideia de pesquisa binária, nomeadamente, queremos saber dado um valor de $T$, quantos segmentos têm média (arredondada) menor ou igual a $T$. Já vimos que se respondermos a esta pergunta eficientemente, então temos a solução do problema.

Vamos agora pensar no seguinte, que segmentos têm média menor ou igual a $T$? Vamos supor que o segmento de $i$ a $i + X - 1$ tem média menor ou igual a $T$, isto significa que:

$$ \frac{S_i + S_{i + 1} + \ldots S_{i + X - 1}}{X} \leq T $$

Se trabalharmos a expressão anterior, vemos que:

$$ S_i + S_{i + 1} + \ldots S_{i + X - 1} - T\cdot X \leq 0 $$

O que finalmente implica que:

$$ (S_i - T) + (S_{i + 1} - T) + \ldots (S_{i + X - 1} - T) \leq 0 $$

Dado um valor de $T$, vamos definir então a sequência $S'$ como: $S'_i = S_i - T$. Então a média do segmento entre $i$ e $i + X$ em $S$ é menor ou igual a $T$ se e só se a soma do segmento entre $i$ e $i + X$ em $S'$ é menor ou igual a 0. Isto implica que podemos usar as ideia da Parte II aplicadas a $S'$ para resolver a Parte III! Mas há um problema: na Parte II os elementos da sequência eram sempre positivos (isto é era muito importante no nosso cálculo de $X_i$!), mas agora podem ser negativos, por isso a mesma solução não funciona.

Recapitulando, o nosso objetivo é agora fazer o seguinte: dado $T$, quantos segmentos de $S'$ tem soma menor ou igual a 0. Para isto, vamos analisar um objeto importante, nomeadamente a array de somas parciais (também conhecida como somas acumuladas). Esta é definida da seguinte forma:

$$ P_i = S'_1 + S'_2 + \ldots S'_i $$

É muito fácil calcular esta array em tempo $O(N)$, basta reparar que para $i > 1$, $P_i = S'_i + P_{i - 1}$, e um ciclo basta-nos. Por simplicidade, vamos assumir que $P_0 = 0$. Agora, vamos ver o seguinte: qual é a relação entre a $P$ e soma dos elementos entre $i$ e $i + X - 1$? Ora, podemos facilmente observar o seguinte:

$$ S'_i + S'_{i + 1} + \ldots S'_{i + X - 1} = P_{i + X - 1} - P_{i - 1} $$

Isto implica que, se a soma do segmento entre $i$ e $i + X - 1$ é menor ou igual a 0, então $P_{i - 1}$ é maior ou igual que $P_{i + X - 1}$. Perfeito! Isto significa que temos de encontrar todos os pares de índices $i, j$ onde $i < j$ e $P_i \geq P_j$.

Dada uma array qualquer $P$, o número de pares de índices $i, j$ onde $i < j$ e $P_i \geq P_j$ é conhecido como o número de inversões de $P$. Há várias formas eficientes de calcular este número eficientemente, leia-se, em tempo $O(N \log N)$. Uma possível usa uma modificação pequena do algoritmo de merge sort, que foi abordado num dos artigos introdutórios. Para mais informações sobre como fazê-lo, podem consultar o livro Competitive Programmer’s Handbook, nomeadamente o Capítulo 3 a Secção Inversions. A outra forma comum de calcular inversões utiliza uma estrutura de dados eficiente, por exemplo, uma Fenwick Tree ou uma Segment Tree.

Análise da solução

Assim como a solução da Parte II, a nossa solução tem duas componentes: uma pesquisa binária de custo $O(\log S_{\max})$ (para a Parte III este custo pode ser ligeiramente melhorado, consegues ver como?); o cálculo do número de inversões em $P$, de custo $O(N \log N)$. Logo a complexidade temporal total é de $O(N\log N \log S_{\max})$. Isto é suficiente para resolver a única subtarefa da terceira parte e obtém assim os 25 pontos desta parte.