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:

Strings e Vetores

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:

DFS ou BFS

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:

Ambos os vértices são pedras;
O pulo que o Sapo dá para ir de uma pedra para a outra é paralelo a um dos lados do lago;
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:

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.

Plano de estacionamento

Conhecimento prévio necessário:

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

Para o $i$ -ésimo cliente, encontre a maior vaga não-ocupada menor ou igual a $V_i$ ;
Caso não exista nenhuma vaga não-ocupada menor ou igual a $V_i$ , termine o programa;
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: