Comentário NOIC OBI – Fase 3 – Festa

Escrito por Pedro Racchetti

Conhecimentos utilizados:

• Vector da STL
• Segment Tree e Busca Binária na Segment Tree (Utilizadas na parcial 2)

Esse problema apresentou 4 pontuações parciais, que serão discutidas separadamente.

Parcial 1 ($N \leq 100$ e $M \leq 10$)

Para essa parcial, podemos inicializar um $vector$ com todas as posições iniciais, e remover as posições apropriadas do $vector$, usando a função $erase()$. Note que precisamos pré-computar os itens a serem removidos, para se manter a ordem das posições.

A função $erase()$ em um $vector$, ao contrário de um $set$, por exemplo, tem complexidade $O(N)$, e como, independente de $M$, cada elemento inicial será removido no máximo uma vez, essa solução tem complexidade $O(N^2 + M)$. Segue o código, para melhor compreensão.

Parcial 2 ($N \leq 4 * 10^5$ e $M \leq 5000$)

Para essa parcial, podemos adaptar a solução anterior, porém ao invés de se manter um $vector$ com os elementos ainda ativos, podemos manter uma Segment Tree, que irá manter, para cada posição da fila inicial, 1 se a posição estiver ativa, e 0 se não. Dessa forma, a soma de prefixo de uma certa posição ativa indica o número da posição na fila após alguns passos.

Numa árvore de segmentos, podemos “remover” uma posição, ou seja, transformar seu valor em 0, com complexidade de $O(log{}_ N)$, e encontrar qual é o i-ésimo valor ativo também em $O(log N)$, usando Busca Binária, adaptada para a árvore de segmentos. Dessa forma, como um número pode apenas ser removido da fila uma vez, temos uma complexidade total de $O(M + N \cdot log{}_ N)$. Segue o código, para melhor compreensão.

Parcial 3 ($t_i = 2$, para todo $i$)

Observação: essa parcial pode ser considerada mais fácil que a anterior, mostrando a importância de sempre ler todas as parciais de um problema, quando não se sabe resolvê-lo inteiro, já que as parciais não estão necessariamente em ordem crescente de dificuldade.

Para essa parcial, é útil se observar padrões. Observe o caso de $N = 25$ e $M = 3$

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 <- Inicial
• 1 3 5 7 9 11 13 15 17 19 21 23 25 <- Após o primeiro passo. Sobraram apenas números da forma $2k + 1$
• 1 5 9 13 17 21 25 <- Após o segundo passo. Sobraram apenas números da forma $4k + 1$
• 1 9 17 25 <- após o terceiro passo. Sobraram apenas números da forma $8k + 1$, ou seja $2^3 + 1$

Nota-se então, que após o k-ésimo passo, sobram apenas os números de forma $2^k + 1$. Isso não é uma demonstração formal, porém essa é relativamente fácil de se encontrar, por meios de indução. Note também que, para $M \geq 31$, $M$ passos, não haverão mais números possíveis, exceto o $1$.

Essa solução tem complexidade $O(M)$, porém com $M \geq 31$, temos complexidade $O(1)$. Segue então o código, para melhor compreensão.

Parcial 4 (Sem restrições adicionais)

Agora, chegamos a cereja do bolo: o problema completo!

Vamos mais uma vez analisar um caso, dessa vez, $N = 20$, $M = 2$, $t_1 = 2$ e $t_2 = 3$.

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
• 1 3 5 7 9 11 13 15 17 19
• 1 3 7 9 13 15 19

Dessa vez, o padrão não é tão evidente. Observe porém, se olharmos apenas as posições da fila de cada passo, não seu valor original, e X para as posições removidas.

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
• 1 X 2 X 3 X 4 X 5 X  6   X   7   X  8   X  9  X  10  X
• 1 2 3 4 5 6 7 8 9 10  <- após as remoções do primeiro passo.
• 1 2 X 3 4 X 5 6 X 7
• 1 2 3 4 5 6 7 <- Após as remoções do segundo passo

Não é óbvio o que acontece com uma posição quando progredimos de um passo para o próximo. Porém, observe o que acontece com uma posição quando regredimos de um passo para o anterior: o valor no passo anterior da posição é somente a posição, somada ao número de X antes dela! Ou seja, como sabemos que os números finais são limitados, conseguimos fazer as operações em reverso. Basta agora saber quantos X haverão antes de uma posição qualquer em um passo. Para isso, perceba que, entre o i-ésimo e o i+1-ésimo passo haverá um X a cada $t_i$ números. Porém, após o i-ésimo passo, todos os X que estavam sendo contados são removidos, então, para regredir, se adiciona um X a cada $t_i - 1$ números para todos os anteriores a um índice específico. Logo, serão adicionados $\frac{pos-1}{t_i - 1}$ números anteriores a $pos$ ao se regredir de um passo para o anterior.

Dessa forma, conseguimos calcular qual seria a posição inicial de cada posição final após todos os passos. Essa solução tem complexidade $O(S*M)$, onde S é o tamanho do conjunto dos números da saída. Segue o código, para melhor compreensão.