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:

Strings

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.

Clique aqui para ver o código

Frações Binárias

Comentário escrito por Murilo Maeda

Conhecimento prévio necessário

Soma máxima em intervalo

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:

DP em árvore

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:

Conhecimento de programação Dinâmica

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$ .

Clique aqui para conferir o código