OBOI 2023 – Fase 2 – Nível Sênior
Se você quiser se preparar para a OBI, não deixe de conferir o Roteiro de estudos de informática, e também a página de informática do NOIC, com todos nossos materiais.
Para conferir a prova na íntegra, clique aqui.
Cifra
Comentário escrito por João Pedro Castro
Conhecimento prévio necessário:
Vamos denotar o i-ésimo caractere de uma string $$S$$ como $$S_i$$ (0-indexado). A ideia da solução é simplesmente checar se a “distância” entre todos os pares de caracteres $$S_i$$ e $$T_i$$ são a mesma para todo $$0 \leq i < |S, T|$$. Para realizar isso, podemos simplesmente guardar a distância entre os primeiros caracteres de ambas strings, $$S_0$$ e $$T_0$$, e depois adicionar essa distância à todo $$T_i$$ e confirmar se após isso ele é o mesmo caractere que $$S_i$$.
Para não termos distâncias negativas, se $$S_0 < T_0$$ dizemos que $$S := T$$ e que $$T := S$$ simultaneamente (ou seja, trocamos elas de lugar); e para somar essa distância $$d$$ nos $$T_i$$ podemos transformar eles em valores númericos entre $$0$$ e $$25$$ fazendo $$T_i – \text{‘A’}$$, e então somar a esse valor a distância $$d$$, e depois pegar o módulo $$26$$ disso, para que caso passe da letra Z ele volte para o A. Logo, o caractere após a soma vai ser $$((T_i – \text{‘A’}) + d + \text{‘A’})~mod~26$$, e se esse valor for igual a $$S_i$$ para todo $$T_i$$, a resposta é ‘S’, caso contrário a resposta é ‘N’.
Clique aqui para conferir o código
Permutação Máxima
Comentário escrito por Caique Paiva
Conhecimentos Prévios Necessários:
- Algoritmos Gulosos
A ideia do problema é bem simples. Depois de fazer alguns casos na mão ($$n = 2, 3, 4$$), você vê que a resposta nesses casos vai ser a permutação $$[N, N-1, \cdots, 1]$$ (para $$n = 2 \rightarrow [2, 1]$$ é a resposta, para $$n = 3 \rightarrow [3, 2, 1]$$ é a resposta, e assim vai). Durante a prova, a ideia não é provar isso, mas você codar e torcer para isso ser a resposta, já que não tem penalidade para WA. Dito isso, é possível provar, embora ela seja meio complicada, então só recomendo pensar na prova caso você também se interesse por matemática olímpica.
Para implementar, basta criar uma variável $$res= 0$$, e fazer um for de $$n$$ até $$1$$ fazendo $$res += |n-i+1 – i|$$. Veja que $$res$$ pode ficar bem grande, então é importante criar ele como uma variável long long.
Frações Binárias
Comentário escrito por Murilo Maeda
Conhecimento prévio necessário
Solução
A observacão principal que é necessária nesse problema é que uma fração cujo denominador e numerador são potências de 2 pode ser escrita simplesmente como uma potência de 2. Por exemplo, uma fração $$\frac{2^x}{2^y}$$ pode ser escrita como $$2^{x – y}$$. Agora, temos que achar o intervalo de um produto de potências de 2 com o maior produto possível. Para fazer isso, basta perceber que quando multiplicamos potências de mesma base, simplesmente somamos os expoentes para obter o resultado. Mais especificamente, $$2^x * 2^y = 2^{x + y}$$. Então, se quisermos o intervalo com maior produto, basta encontrar o intervalo com maior soma dos expoentes. Ou seja, basta fazer uma dp de Kadane nos expoentes!
Cuidados Adicionais
Um problema que ainda temos é que obtemos a resposta em termos do expoente do resultado final. Como há no máximo $$10^5$$ frações e o expoente pode ir até $$15$$, o expoente da resposta pode chegar até $$10^5 * 15$$, que ultrapassa o limite de long long. Então, não é possível simplesmente calcular a resposta elevando 2 à resposta que achamos da dp e depois tirar módulo $$10^9 + 7$$, precisamos ir calculando a resposta aos poucos e ir calculando o módulo. Note que só podemos tirar módulo de produtos dessa forma porque $$10^9 + 7$$ é primo.
Clique aqui para conferir o código
Árvore com Macacos
Comentário escrito por Arthur Lobo
Conhecimento prévio necessário:
A ideia é enraizar a árvore no vértice 1 e fazer uma DP em árvore que vai ser $$dp(u,flag) = $$ maior quantidade de vértices bloqueados na subárvore do $$u$$, com $$flag$$ representando alguma condição. $$flag$$ pode ser $$0,1$$ ou $$2$$.
- $$dp(u,0) = $$ maior quantidade de bloqueados na subárvore do $$u$$ e sem precisar mandar um macaco para o pai.
- $$dp(u,1) = $$ maior quantidade de bloqueados na subárvore do $$u$$ e termina com um macaco no $$u$$ (que pode ser mandado para o pai).
- $$dp(u,2) = $$ maior quantidade de bloqueados na subárvore do $$u$$ e começa com uma pedra em $$u$$ que foi mandada pelo pai.
Agora vamos olhar para as transições. Vão ter dois casos:
O primeiro é quanto o vértice $$u$$ começa com um macaco. Nesse caso:
- $$dp(u,2) = -inf$$, porque é impossível que o pai de $$u$$ mande um macaco para ele, já que ele já começa com um.
- $$dp(u,1) = 1 + \sum dp(v,0)$$. Porque $$u$$ manda seu macaco para seu pai, então ele não pode interagir com os filhos.
- $$dp(u,0) = 1 + (\sum dp(v,0)) + max((-dp(v2,0)+dp(v2,2))$$, para todo $$v2$$ que é filho de $$u$$. $$v2$$ representa qual é o vértice que estamos mandando o macaco que começa em $$u$$.
O segundo caso é quanto o vértice $$u$$ não começa com um macaco:
- $$dp(u,1) = (\sum dp(v,0)) + max((-dp(v1,0)+dp(v1,1))$$, para todo $$v1$$ que é filho de $$u$$. $$v1$$ representa qual é o vértice que manda um macaco para $$u$$.
- $$dp(u,2) = (\sum dp(v,0)) + max((-dp(v2,0)+dp(v2,2))$$, para todo $$v2$$ que é filho de $$u$$. $$v2$$ representa qual é o vértice que estamos mandando o macaco $$u$$ recebe.
- $$dp(u,0) = (\sum dp(v,0)) + max((-dp(v1,0)+dp(v1,1) -dp(v2,0)+dp(v2,2))$$, para todo $$v1,v2$$, tal que $$v1 \neq v2$$ e ambos são filhos de $$u$$. $$v1$$ e $$v2$$ representam, respectivamente, qual vértice manda um macaco para $$u$$ e qual vértice recebe esse macaco mandado.
Em ambos os casos, também é necessário fazer $$dp(u,0):= max(dp(u,0), \sum dp(v,0))$$ ($$+1$$ se for o primeiro caso.
Clique aqui para conferir o código
Vingaça do Leonardo
Comentário escrito por Rafael Nascimento
Conhecimento prévio necessário:
Neste problema não existem muitas parciais interessantes, então comentaremos apenas a solução de 100 pontos. Porém, antes disso, precisamos fazer algumas observações. Vamos iniciar com a operação $$3$$:
1º ) A operação $$3$$ dobra o tamanho da string. Trivial de provar, já que cada caractere é substituído por $$2$$ caracteres.
2º) Existem no máximo $$log |S|$$ operações de tamanho $$3$$. Trivial de provar considerando a observação $$1$$.
Agora vamos analisar as outras operações:
As operações $$1$$ e $$2$$ são equivalentes ao std::deque, e algo fundamental é observar que não é possível alterar strings internas: ou seja, podemos adicionar caracteres apenas em áreas que ainda não foram “criadas” (as extremidades).
Não só isso, como podemos falar o seguinte:
Digamos que exista um array $$H[i]$$. Esse array representa o caractere que gerou o $$i$$. Por exemplo, se um caractere $$j=0$$ foi dobrado $$2$$ vezes, ou seja, virou $$0110$$, afirmaremos que esses $$4$$ caracteres foram gerados por $$j$$. Dessa forma o $$H[i]$$ de todos os caracteres é igual a $$j$$.
Agora definamos o array $$T[i]$$. Este array existe apenas para caracteres “originais”, ou seja, $$H[i]=i$$. Este array armazena o numero de vezes que o caracteres $$i$$ foi afetado por operações de dobra. Observe que $$T[i]\leq log|S|$$
Por fim, criamos o array $$A[i] = T[H[i]]$$. É possível provar que o array $$T[i]$$ é unimodal. Ou seja, ele primeiro é não-decrescente, atinge um pico $$m$$, e vira não-crescente. De forma mais técnica, $$T[i-1]\leq T[i]$$ se $$i\leq m$$ e $$T[i-1]\geq T[i]$$ se $$i\geq T[i]$$.
Essas informações já são suficientes para montarmos nossa programação dinâmica.
Primeiro, vamos analisar os estados. Temos que armazenar:
A posição atual que estamos na string, o nosso $$i$$. Esse valor vai até $$|S|$$.
O valor atual de $$T[i]$$. Como dito anteriormente, esse valor vai até $$log |S|$$.
Uma variável booleana indicando a direção do array (se ele está antes do pico, sendo não-decrescente, ou depois do pico, sendo não-crescente).
Para a transição nós temos que fazer as seguintes condições:
- O $$T[i]$$ alterou. Chamamos $$f(pos, novo T[i], direcao)$$. Devemos somar $$1$$ caso a direção seja não-decrescente e subtrair $$1$$ caso seja não-crescente.
- A direção se alterou de não-decrescente para não-crescente. Chamamos $$f(pos,T[i], nova direcao)$$. Note que esta troca acontece apenas uma vez.
- Caso a string seja válida, isto é, a substring que inclui $$[pos,pos+2^(T[i])]$$ (ou seja, a substring gerada pelo caractere original) seja igual a substring esperada (a substring que seria gerado caso um caractere $$0$$ ou $$1$$ fosse submetido à $$T[i]$$ operações), podemos andar com a nossa função, indo para $$f(pos+2^{T[i]},T[i],direcao)$$. Podemos checar se a substring é válida com o hash, apenas tome cuidado pois o risco de colisão é alto. Provavelmente será necessário utilizar múltiplos hashes (de acordo com nossos testes, 5 hashes distintos são suficientes).
Calculando a complexidade:
Nós possuímos $$O(N\cdot log N)$$ estados na nossa programação dinâmica. Considerando que caso implementemos um hash $$O(1)$$ podemos ter uma transição em $$O(1)$$, a complexidade final é $$O(N\cdot log N)$$. Soluções $$O(N \cdot log^2 N)$$ devem receber AC, considerando que $$|S|\leq10^5$$.