Soluções da Qualificação das ONI'2020
Problema C - Rua das Flores
Tipo de problema: Pesquisa Binária
Autor do problema: Kevin Pucci (Universidade do Porto - ICBAS)
Dificuldade do problema: Médio-Difícil
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:
1 ≤ $N$ ≤ $10^5$ | Comprimento da rua |
1 ≤ $K$ ≤ $N$ | Número de segmentos a considerar |
1 ≤ $S_i$ ≤ $10^9$ | Custo de um metro de rua |
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:
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:
1 ≤ $N$ ≤ $10^5$ | Comprimento da rua |
1 ≤ $K$ ≤ $N(N + 1) / 2$ | Número de segmentos a considerar |
1 ≤ $S_i$ ≤ $10^9$ | Custo de um metro de rua |
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:
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).
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:
1 ≤ $N$ ≤ $10^5$ | Comprimento da rua |
1 ≤ $K$ ≤ $N(N + 1) / 2$ | Número de segmentos a considerar |
1 ≤ $S_i$ ≤ $10^9$ | Custo de um metro de rua |
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.