OBI 2021 - Fase 2 Turno B - 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!

Comentário escrito por Lúcio Figueiredo, Pedro Racchetti, Thiago Mota e Luca Dantas

Para conferir a prova na íntegra, clique aqui.

Cálculo rápido

Conhecimento prévio necessário:

• Estruturas Condicionais
• Loops

Para resolver este problema, precisamos pensar em como podemos calcular a soma dos dígitos de um número $X$ de forma eficiente. Ou seja, dado um número $X$, precisamos encontrar cada um dos dígitos de $X$ individualmente; feito isso, é fácil calcular a sua soma.

Algortimo para encontrar os dígitos de $X$

Para extraírmos cada um dos dígitos de $X$, podemos utilizar o seguinte algoritmo:

1. Encontre o último dígito $d$ de $X$;
2. Remova o dígito $d$ de $X$. Denote o número resultante por $X'$;
3. Se $X'$ não possuir dígito algum, termine o algoritmo. Senão, repita o passo 1 com o novo número $X'$.

Apesar do algoritmo acima estar correto, ainda é necessário descobrir como calcular o último dígito de $X$ e como removê-lo.

Encontrar o último dígito de $X$

Seja $q$ o quociente e $r$ o resto na divisão de $X$ por $10$. Com esta definição, temos que $X = 10 \cdot q + r$. Observe que como $10 \cdot q$ é um múltiplo de $10$, o seu último dígito é igual a $0$. Além disso, como $r$ é o resto da divisão de $X$ por $10$, temos que $0 \leq r \leq 9$. Portanto, podemos concluir que o valor $r$ é igual ao último dígito de $X$ em sua representação decimal! Para observar isto, considere os seguintes exemplos:

$X = 21$: $q = 2, r = 1$. Último dígito de $21$ é igual a $1$.

$X = 343$: $q = 34, r = 3$. Último dígito de $343$ é igual a $3$.

$X =78900$: $q = 7890, r = 0$. Último dígito de $78900$ é igual a $0$.

Com esta observação, concluímos que o último dígito de $X$ é igual a $X \% 10$, já que o operador $\%$ calcula o resto da divisão de um inteiro por outro.

Remover o último dígito de $X$

Como $r$ é o último dígito de $X$ e $X = 10 \cdot q + r$, podemos observar que $q$ é igual ao valor $X'$ - ou seja, o valor resultante da remoção do último dígito de $X$. Novamente, considere os seguintes exemplos para melhor entendimento:

$X = 21$: $q = 2, r = 1$. $X'$ é igual a $2$.

$X = 343$: $q = 34, r = 3$. $X'$ é igual a $343$.

$X =78900$: $q = 7890, r = 0$. $X'$ é igual a $7890$.

Para encontrar o valor $q$, observe que, por definição, ele é igual a $\frac{X-r}{10}$. Porém, como $r < 10$, temos que $\frac{X-r}{10}$ é igual à parte inteira de $\frac{X}{10}$. Portanto, o valor $X' = q$ é igual a $X / 10$, já que o operador $/$ calcula a parte inteira da divisão.

Agora que sabemos como executar cada passo do algoritmo apresentado acima, basta o utilizarmos para encontrar a soma dos dígitos de $X$.

Complexidade do algoritmo

Observe que a complexidade do algoritmo acima é proporcional à quantidade de dígitos de $X$. Portanto, como a quantidade de dígitos de $X$ é menor ou igual a $\log_{10} X + 1$, a complexidade final do algoritmo é $O(\log_{} X)$.

Etapa final

Agora que possuímos um algoritmo eficiente para encontrar as somas dos dígitos de um número inteiro, o que sobra para terminarmos o problema é executá-lo para cada inteiro $X$ entre $A$ e $B$, utilizando um loop For. Caso a soma dos dígitos de $X$ seja igual a $S$, adicionamos $1$ em uma variável de resposta, e imprimimos o seu valor ao final do código.

Como executamos o algoritmo acima em todos os números entre $A$ e $B$, a complexidade final da solução é $O((B-A+1) \cdot \log_{} B) = O(B \cdot \log_{} B)$. Para melhor entendimento, confira o código abaixo:

Lista palíndroma

Conhecimento prévio necessário:

• Two Pointers
• Vetores

Antes de resolver o problema, podemos fazer algumas observações iniciais. Para uma subarray $L[i...j]$, com $i \leq j$ da lista fornecida, note:

• Se $i = j$, então o número de operações necessárias é $0$;
• Se $L[i] = L[j]$, não precisamos fazer uma operação, bastando resolver o problema para a subarray $L[i+1...j-1]$;
• Se $L[i] < L[j]$, precisamos aumentar $L[i]$. Dessa forma, precisamos fazer uma operação de contração com o consecutivo de $i$. A mesma ideia se aplica para o caso de $L[i] > L[j]$, fazendo a operação entre $j$ e $j-1$.

Podemos então usar as observações do algoritmo de Two Pointers indicado no link acima, usando como subarray o intervalo $L[1...n]$ - ou seja, a lista inteira. Usaremos então $it1$ como o primeiro ponteiro, começando no início da lista, e $it2$ como segundo ponteiro, começando no fim da lista, até que se encontrem pelas operações acima.

A complexidade final da solução é $O(n)$. Segue o código comentado, para melhor compreensão:

Poligrama

Conhecimento prévio necessário:

• Vetores
• Divisores e Fatoração

A ideia para resolver este problema é utilizar o fato de que todas as substrings devem ter o mesmo tamanho, pois todas elas tem que ser um anagrama da raiz. Portanto, o tamanho da raiz tem que ser um divisor de $n$. Iremos então pecorrer todos os tamanhos possíveis da raiz e testar se aquela raiz é uma resposta válida.

Para comparar se duas strings são anagramas, podemos olhar se as frequências de cada letra são as mesmas nas duas strings. Com isso, para cada possível tamanho da raiz, podemos olhar a string e conferir se todas as substrings são anagramas da raiz. Já que para cada divisor de $n$, nós conferimos se ele é uma resposta em $O(n)$, a complexidade final é $O(n \cdot d)$, sendo $d$ o número de divisores de $n$.

Na aula de Teste de Primalidade, Divisores e Fatoração, podemos ver que o número de divisores de um número é por volta de $O(\sqrt{n})$ (embora na maioria das vezes o número de divisores é bem menor do que este valor). Portanto, a complexidade final é $O(n \sqrt{n})$. Segue a implementação do código:

Senha da Vó Zinha

Conhecimento prévio necessário:

• Vetores
• Ordenação

Para a resolução desse problema precisamos analisar algumas propriedades da comparação lexicográfica de duas strings. Como a comparação vai da esquerda para a direita se nós sabemos que, se existe um conjunto de substrings $A$ com um prefixo menor lexicograficamente que outro conjunto de substrings $B$, todos os elementos do conjunto $A$ aparecem antes na lista que todos os elementos do conjunto $B$. Portanto, se analisarmos cada posição em que temos uma escolha a fazer, sabemos quantas possibilidades existem para cada escolha e a ordem relativa entre esses grupos.

Por exemplo, se temos a string $\cdot \cdot a$ e as palavras $ab$ e $cde$, sabemos que existem três strings com o prefixo $a$ e três strings com o prefixo $b$. Logo, podemos definir qual a letra de cada posição à medida que andamos da esquerda para a direita da seguinte maneira: Vamos dizer que queremos a $p$-ésima permutação e temos $j$ possibilidades nessa posição, e, para cada uma dessas escolhas, temos $q$ possibilidades para o resto da string. Desta forma, sabemos que o número de strings possíveis no total é $j \cdot q$. Como sabemos a posição relativa de cada letra, podemos decidir qual das $j$ possibilidades é a correta olhando o valor de $\left\lfloor { \dfrac{p}{q} } \right\rfloor$ (0-indexado), pois se for uma das $q$ primeiras possibilidades, a letra correta é a primeira; se for entre as possibilidades $[q+1, 2q]$, a letra correta é a segunda, e assim por diante. Depois que decidirmos a letra atual, basta continuarmos com o mesmo problema em versão reduzida para escolher a próxima letra, com o próximo valor de $p$ sendo $p$ $mod$ $q$ (resto da divisão de $p$ por $q$).

O único detalhe final é que a quantidade de possibilidades pode ser muito grande, ultrapassando o limite de um inteiro de 64 bits (o valor pode chegar até $26^{500}$). Portanto, pode acontecer que em algumas das primeiras letras não seja possível calcular qual a letra utilizando o algoritmo apresentado acima. Porém, nós podemos nos fazer valer de que, como para um prefixo da string o valor de $q >> p$ a letra a ser escolhida sempre será a primeira, só precisaremos responder qual a letra a ser escolhida para um sufixo da string. Para escolher esse sufixo basta percorrermos a string de trás pra frente e contar quantas possibilidades existem só no sufixo atual; caso esse valor seja maior ou igual a $p$, encontramos o que queríamos e podemos começar o algoritmo. Senão, continuamos andando para a esquerda.

Segue o código para melhor entendimento: