Problema A - Tesouros de Kilmia

O Problema

Dado um conjunto de $N$ arcas da linha de Algor, a posição inicial do Daniel $B$ e um conjunto de instruções sobre o movimento do Daniel, calcula quantos tesouros o Daniel recolhe.

Restrições

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

1 ≤ $N$ ≤ 100 000	Número de arcas
1 ≤ $B$ ≤ $N$	Posição inicial
1 ≤ $I$ ≤ 100 000	Número de instruções

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

Grupo	Número de Pontos	Restrições adicionais
1	25	1 ≤ $N$ ≤ 100, 1 ≤ $I$ ≤ 100
2	20	1 ≤ $I$ ≤ 3 000
3	20	1 ≤ $N$ ≤ 3 000
4	35	-

Solução Base

Este problema pedia-nos que determinassemos por quantos tesouros diferentes o Daniel passa, após seguir um conjunto de instruções.

A solução mais simples passa por simular diretamente cada instrução, mantendo uma variável que representa a posição atual do Daniel e fazendo um ciclo por instrução para avançar as posições indicadas e verificar se existe algum tesouro em cada posição passada. Finalmente, é apenas preciso ter cuidado para marcar cada tesouro como recolhido depois de o recolher, para não contarmos duas vezes o mesmo tesouro.

Em termos de eficiência, para cada instrução podemos ter que percorrer $N$ posições (se a instrução obrigar a percorrer grande parte da linha de arcas), por isso no fim fazemos $I N$ operações totais (para saber mais como funciona este tipo de análise ver o artigo de análise de complexidade).

Esta seria uma solução $O(I N)$ que daria aproximadamente 60 pontos.

Solução Ótima

Para melhorar a solução anterior, é preciso pensar um pouco sobre o que está a acontecer no problema e assim fazer uma observação importante: o Daniel cobre sempre um intervalo contígo de posições. Se a posição mais à direita que o Daniel chegou foi a posição $p_d$, então o daniel teve que passar por todas as posições de $B$ a $p_d$, pois ele nunca "salta" posições. Analogamente, se a posição mais à esquerda que o Daniel chegou foi a posição $p_e$, então o daniel teve que passar por todas as posições de $p_e$ a $B$.

Assim, sabendo $p_e$ e $p_d$, basta fazer um ciclo a percorrer todas as posições entre $p_e$ e $p_d$ e calcular quantos tesouros há nesse intervalo. Para calcular $p_e$ e $p_d$, basta calcular a posição após seguir cada instrução e manter a menor e maior, respetivamente.

Em termos de eficiência, isto corresponde a um ciclo para processar todas as instruções e calcular $p_e$ e $p_d$, e a um segundo ciclo para verificar as arcas entre $p_e$ e $p_d$, o que corresponde a $I + N$ operações.

Esta seria uma solução $O(I + N)$ que daria os 100 pontos.