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$$, $$2^M + 1 > 10^9$$, então, após $$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.