Comentário NOIC OBI 2021 – Fase 3 – Programação Nível 1

OBI 2021 – Fase 3 – Programação Nível 1

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Comentário escrito por Pedro Racchetti, Lúcio Figueiredo e Leonardo Paes

Para conferir a prova na íntegra, clique aqui.

Casamento de inteiros

Conhecimento prévio necessário:

Inicialmente, leremos $$A$$ e $$B$$ como strings e ajustaremos seus tamanhos adicionando zeros à esquerda até que o tamanho de $$A$$ seja igual ao tamanho de $$B$$. Em seguida, vamos delcarar duas strings $$ans_A$$ e $$ans_B$$ que guardarão os valores $$A$$ e $$B$$ após o casamento. Após isso, iteraremos por cada dígito (ou caractere) de $$A$$ e $$B$$ e iremos compará-los assim como indicado no enunciado do problema, adicionando os dígitos resultantes do casamento em $$ans_A$$ ou $$ans_B$$. Por fim, precisamos remover quaisquer zeros à esquerda restantes em $$ans_A$$ e $$ans_B$$; para isso, usaremos a função $$stoi()$$, que transforma strings em inteiros e remove zeros à esquerda.

A complexidade da solução é $$O(max(digitos_A, digitos_B))$$. Confira o código abaixo para melhor compreensão:

Sr. Sapo

Conhecimento prévio necessário:

Para resolvemos esse problema, podemos visualizar a matriz dada como um grafo. Cada célula $$(i, j)$$ da matriz será um vértice do grafo. Haverá uma aresta entre dois vértices se, e somente se,  as três condições a seguir forem verdadeiras:

  1. Ambos os vértices são pedras;
  2. O pulo que o Sapo dá para ir de uma pedra para a outra é paralelo a um dos lados do lago;
  3. A distância do pulo é menor ou igual a $$3$$.

Segue uma imagem mostando todas as arestas partindo de um vértice arbitrário $$(i, j)$$, supondo que todos os vértices sejam pedras:

Após criado tal grafo, basta utilizar algum algoritmo de busca em grafos, como por exemplo uma DFS ou uma BFS. Iniciamos o algoritmo na posicão inicial do Sapo. Se em qualquer momento visitarmos a posição final, sabemos que é possível para o Sapo chegar lá; caso contrário, é impossível!

A complexidade da solução é $$O(N \cdot M)$$. Confia o código abaixo para melhor compreensão:

Festa olímpica

Conhecimento prévio necessário:

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.

Plano de estacionamento

Conhecimento prévio necessário:

Para resolver este problema, usaremos a seguinte estratégia gulosa:

  1. Para o $$i$$-ésimo cliente, encontre a maior vaga não-ocupada menor ou igual a $$V_i$$;
  2. Caso não exista nenhuma vaga não-ocupada menor ou igual a $$V_i$$, termine o programa;
  3. Caso contrário, marque a vaga encontrada como ocupada e repita o algoritmo para o cliente seguinte.

A intuição por trás do funcionamento desta estratégia é que, para cada cliente, sempre selecionaremos a sua “pior” vaga possível. Em outras palavras, ao escolhermos a maior vaga possível para um cliente, tornamos o conjunto de vagas não-ocupadas melhor possível para clientes futuros (já que uma vaga de menor índice acomoda todos os clientes que uma vaga maior também acomodaria).

Para implementar o algoritmo acima, basta utilizarmos um set: Inicialmente, inserimos no set todas as $$N$$ vagas; em seguida, podemos encontrar a maior vaga menor ou igual a $$V_i$$ utilizando a função upper_bound implementada no set (mais detalhes no código abaixo); por fim, removemos a vaga encontrada (se existir) utilizando a função erase.

Como as operações realizadas no set possuem complexidade $$O(\log_{} N)$$, a complexidade da solução é $$O(M \cdot \log_{} N)$$. Confira o código abaixo para melhor compreensão: