OBI 2021 - Fase 3 - Programação Nível 2

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

Escrito por Pedro Racchetti, Luca Dantas, Lúcio Figueiredo, Anita Almeida 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:

Cubo e quadrado

Conhecimento prévio necessário

Loops

Inicialmente, note que a quantidade de cubos perfeitos menores ou iguais a $10^8$ é pequena; mais especificamente, esta quantidade é menor ou igual a $\sqrt[3]{10^8} < 465$ . A partir desta observação, iremos iterar pelos inteiros $k$ maiores ou iguais a $1$ tais que $k^3 \leq B$ . Em seguida, basta checarmos se $k^3$ é maior ou igual a $A$ e se é ou não um quadrado perfeito; se sim, encontramos mais uma resposta. Para checar se $k^3$ é um quadrado perfeito, usaremos a função $sqrt()$ , que retorna a parte inteira da raíz quadrada de um inteiro.

A complexidade da solução é $O(\sqrt[3]{B})$ . Confira o código abaixo para melhor entendimento:

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.

Falha de segurança

Conhecimento prévio necessário:

Guia de Estrutura de Dados: Vector, Set e Map

Para esse problema, precisamos calcular quantas vezes uma determinada subsequência de caracteres, que corresponde a uma das senhas fornecidas na entrada, aparece em subsequências das demais senhas fornecidas. A partir disso, basta calcular esse resultado para cada uma das senhas da entrada, somá-los e não esquecer de subtrair ao final as próprias senhas que não podem ser consideradas como uma aparição delas em outras senhas. Veja o seguinte exemplo com apenas 3 senhas na entrada e suas subsenhas possíveis:

noic -> n ; o ; i ; c ; no ; oi ; ic ; noi ; oic ; noic

noi -> n ; o ; i ; no ; oi ; noi

oi -> o ; i ; oi

Assim, obtemos as seguintes opções e suas quantidades:

n=2 ; o=3 ; i=3 ; c=1 ; no=2; oi=3; ic=1; noi=2; oic=1; noic=1

A partir disso, se analisarmos a quantidade encontrada de cada senha na nossa lista de subsenhas, que é o que realmente importa na resposta final, temos:

noic=1; noi=2 ; oi=3

Aqui há uma observação importante que se trata do que foi dito no começo da solução: subtrair o valor $N$ da resposta ao final, já que uma das subsenhas encontradas de cada senha já é a própria senha. Nesse caso, podemos subtrair $1$ em cada resultado previamente ou ao final e obteremos:

noic=0; noi=1 ; oi=2

Se somarmos esses resultados, teremos res = 0+1+2 = 3, que é a resposta final, já que a senha noic pode acessar as duas demais senhas (noi e oi) e a senha noi ainda pode acessar a senha oi.

Assim, o problema se resume em gerar todas as subsequências possíveis de cada senha com auxílio de um $vector$ e de um $set$ , armazenar a quantidade de cada subsequência em um $map$ de $string$ com $int$ e ao final somar a quantidade encontrada para cada senha da entrada.

A complexidade da solução é $O(N \cdot comprimento\_max^2 \cdot \log_{} N)$ . Segue o código comentado para melhor compreensão da solução:

Dona Minhoca

Conhecimento prévio necessário

Ideia 3 - Diâmetros e Centros de Árvores

Observações iniciais

O problema nos fornece uma árvore e inicialmente quer que encontremos o tamanho do "maior ciclo" que podemos obter com a adição de somente uma aresta. Vamos tentar encontrar alguma forma mais simples de encontrar os vértices que uniremos para encontrar esse ciclo.

Suponha que vamos unir dois vértices quaisquer $A$ e $B$ . Queremos conseguir determinar qual o tamanho do ciclo determinado pela união deles rapidamente. Primeiro perceba que o ciclo determinado por cada aresta extra é unicamente definido pela aresta a ser adicionada, pois em uma árvore só existe uma maneira de se ir de um vértice $X$ a um vértice $Y$ qualquer. Portanto, para saber quais vértices farão parte do ciclo, basta verificar quais vértices estão no caminho entre $A$ e $B$ .

Entretanto, como só queremos saber quantos vértices farão parte do ciclo e não necessariamente quais são esses vértices, podemos só utilizar o valor $dist(A, B) + 1$ para denotar o tamanho do ciclo, pois $dist(X, Y)$ normalmente denota a quantidade de arestas entre os vértices e adicionamos 1 para contabilizar o vértice da partida ( $X$ ).

Desse modo, podemos perceber que reduzimos o problema para um problema de diâmetro da árvore, pois só queremos encontrar o máximo valor de distância entre quaisquer dois vértices da árvore e saber quantos pares de vértices têm essa distância entre eles.

Subtask 1: $O(N^2)$

Para essa subtask vamos aplicar diretamente a ideia apresentada no final do parágrafo anterior sem mais nenhuma observação, calculando todas as distâncias entre dois vértices e calculando qual o maior valor e quantos pares têm esse valor de distância.

Segue a implementação dessa ideia para melhor entendimento:

Algoritmo de diâmetro

Para a solução completa vamos ter que realizar algo mais eficiente. Vamos nos recordar de alguns algoritmos padrões utilizados para encontrar o tamanho do diâmetro de uma árvore, para que possamos modificá-los e assim construir um novo algoritmo que também nos forneça quantos diâmetros existem. Um algoritmo promissor é o que será apresentado em seguida e é um algoritmo precursor ao mostrado na aula de Diâmetros e Centros de Árvores.

O algoritmo para encontrar o valor do diâmetro é o seguinte: Para cada vértice iremos tentar achar o maior caminho passando por ele, ou seja, para um vértice $V$ , teremos um caminho que começa em algum vértice da subárvore de um filho de $V$ , denotaremos por $sub(V_{F1})$ , ou no próprio $V$ , passa em algum momento por $V$ em seu menor caminho e termina em algum vértice da subárvore de outro filho de $V$ , $sub(V_{F2})$ .

Para encontrar o maior caminho desse vértice $V$ basta sabermos, para cada filho, qual é o nó mais profundo na subárvore dele, e depois disso juntar os filhos mais profundos e formar assim o maior caminho possível nessa subárvore passando por $V$ . Formalmente a resposta será $dist_{F1} + dist_{F2} + 1$ , onde $dist_{F1}$ e $dist_{F2}$ são os valores de filhos com as duas maiores idstâncias. Segue uma imagem para melhor entendimento:

Perceba que não iremos re-enraizar a árvore completa em todos os vértices, pois só é necessário considerar para cada vértice a sua subárvore, já que, a união dos caminhos considerados por todos os vértices engloba todos os pares possíveis. Cada caminho entre dois vértices vai ser considerado exatamente no menor ancestral comum (LCA) dos dois vértices do caminho, logo cada caminho também só é considerado uma única vez.

Segue a implementação dessa ideia:

Generalizando o algoritmo de diâmetro para a solução completa

Agora vamos explorar o fato citado anteriormente que cada caminho só aparece uma única vez (no LCA entre os vértices do caminho) para não somente encontrar qual o maior valor nesse vértice mas também para contar quantos caminhos têm esse valor máximo.

Para fazer isso a função dfs retornará, além do filho mais distante, quantos filhos na subárvore têm essa distância. Para contarmos no vértice $V$ o número de caminhos máximos iremos fazer algo bem semelhante ao que fizemos no algoritmo anterior, ou seja, salvar quais são as duas maiores distâncias de filhos e combiná-las, utilizando o número de filhos com essa distância (valor retornado pela dfs do filho) para contar quantos pares têm essa distância.

Porém nessa versão generalizada do problema existem mais alguns casos para considerarmos: [1] podem existir diversas subárvores com o valor $dist$ máximo, portanto teremos que considerar todos os pares entre eles; [2] podemos ter também um único filho com valor $dist$ máximo porém vários filhos com o valor de $dist$ sendo o segundo maior possível, logo teremos de combinar todos esses com o maior. Seguem imagens de ambos os casos para melhor entendimento.