OBI 2024 - Fase 2 - Programação Nível 2

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.

Cubo

Comentário por Murilo Maeda Kataoka

Vamos ver como contar os cubos de cada categoria pedida no enunciado:

• Nenhuma face pintada de preto: Os cubos nessa categoria são todos aqueles no "interior" do cubo maior e formam um cubo cujos lados possuem $N - 2$ cubos, onde N é a quantidade de cubos nos lados do cubo maior. Então, há $(N-2)^3$ cubos dessa categoria.
• Exatamente uma face pintada de preto: Os cubos pintados dessa forma são aqueles que estão no meio das faces do cubo maior, nas quais formam quadrados de lado $N - 2$. Como há 6 faces, há $6 * ( N - 2) * (N - 2)$ cubos desse tipo.
• Exatamente duas faces pintadas de preto: Os cubos desse tipo são aqueles que estão nas arestas do cubo maior mas não estão nas quinas. Como há 12 arestas e em cada uma há $(N - 2)$ cubos que não são quinas, há $12*(N-2)$ cubos desse tipo.
• Exatamente três faces pintadas de preto: Os cubos pintados assim são as quinas do cubo maior, que são, no total, 8.

Segue o código:

Alfabeto

Comentário por Murilo Maeda Kataoka

Conhecimento necessário

• STL

Para esse problema, só precisamos de uma estrutura que seja capaz de nos dizer se um certo caracter está ou não no alfabeto. Uma estrutura que faz exatamente isso é o map, da STL do C++. Com ele, basta passarmos pelos caracteres do alfabeto alienígena e marcar $map[caracter] = true$. Depois, quando estivermos passando pela mensagem, basta ver se o map do caracter em questão foi ou não ativado.

Segue o código:

Concatena Dígitos

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

• Somas de prefixos

Vamos chegar em uma fórmula para resolver a pergunta $[L, R]$. Seja $a_i$ o i-ésimo dígito. Veja um número $a_i$ entre $[L, R]$, tem duas possibilidades para ele:

• Ele pode ser um algarismo da dezena, ou seja, ele contribui a soma total com $10 \times a_i$. E caso eu escolha esse número para ser o da dezena, temos $R-L+1-1= R-L$ possibilidades de números para as unidades (Quantidade de números entre $L$ e $R$, sem contar o próprio $a_i$), portanto, temos $R-L$ números com $a_i$ sendo a dezena. Portanto, esse caso adiciona $10 \times a_i \times (R-L)$ nesse caso.
• Agora, esse mesmo número também pode ser um algarismo da unidade, ou seja, ele contribui a soma total com $a_i$. Pelo mesmo argumento acima, temos $R-L$ números com $a_i$ sendo a unidade. Portanto, esse cado adiciona $a_i \times (R-L)$.

Portanto, somando esses dois casos, para cada $a_i$, eles contribuem na resposta o valor $11 \times (R-L) \times a_i$. Fazendo isso para todo $a_i$ entre $[L, R]$, temos que a resposta de uma query é $11 \times (R-L) \times (a_L + \cdots + a_R)$. Agora, usando a técnica de soma de prefixos, faça $p_i = a_1+a_2+\cdots+a_i$, e então, a resposta para query é $11(R-L)(p_R-p_{L-1})$, e conseguimos responder essa query em $O(1)$.

Jogo do Poder

Comentário por Fernando Gonçalves

Conhecimento Necessário:

• Union-Find
• Small to Large no Union-Find

Nesse problema, temos uma matriz $N$ × $M$ em que cada célula tem um poder específico. Uma célula pode ir dominando casas adjacentes de poder menor ou igual, e cada uma dessas adiciona seu poder ao da casa original. Queremos descobrir qual o maior poder que cada uma das casas pode alcançar, ou seja, temos que descobrir qual a soma dos valores das células atingíveis partindo de cada uma das posições da matriz.

Vamos primeiro discutir a ideia unidimensional, daí podemos expandir a solução para duas dimensões, assim resolvendo o problema.

Subtasks 1, 2, 3 e 4 (43 pontos): $N = 1$

Nesta parcial, as células atingíveis de uma casa sempre formarão um intervalo, o qual queremos descobrir para cada posição. Acharemos esses intervalos usando uma Line Sweep e um Union-Find com Small to Large.

No nosso Union-Find guardaremos os intervalos atuais. Para isso, teremos, nessa estrutura, o conjunto de posições "candidatas" em um intervalo e a soma dos poderes nele . Chamamos uma posição de candidata quando ela alcança esse intervalo, ou seja, o intervalo resposta dela contém o intervalo no qual ela está agora.

Inicialmente, haverá $M$ componentes, uma para cada uma das posições do vetor. Então, vamos passar ativando as casas em ordem crescente de poder. Ao acionar uma casa, vamos uni-la com suas adjacências ativas. Para tanto, checamos a soma atual da componente do vizinho que estamos unindo. Se essa soma for menor que poder da casa atual, sabemos que as candidatas desse intervalo não alcançam mais ninguém (porque elas não alcançam a casa atual, que é a menor adjacente ao intervalo delas), então sabemos a resposta delas, e elas deixam de ser candidatas. De qualquer forma, sabemos que a célula atual pode chegar em todos os valores nos intervalos adjacentes, pois, como estes só contém casas ativadas, sabemos que toda casa no intervalo é menor ou igual à atual, então unimos ela aos seus intervalos adjacentes.

Ao final, só precisamos ver quem ainda é candidato no intervalo que cobre o vetor inteiro. As respostas dessas casas será a soma dos poderes de todo o vetor.

Com isso, calculamos a resposta de todo índice no vetor!

Subtasks 5 e 6 (57 pontos):

Agora, precisamos trazer a ideia de $N = 1$ para o caso geral.

Ao invés de ser um intervalo, as células atingíveis formam uma componente, e uma posição também será adjacente às casas de cima e de baixo.

Contudo, essas são as únicas diferenças importantes entre a parcial $N = 1$ e o problema sem restrições.

De fato, a mesma lógica se aplica na matriz: cada componente ainda vai ter candidatas, e essas podem ser removidas também quando uma posição adjacente de soma maior é ativada. Dessa forma, a única adaptação necessária é a das adjacências, o resto não muda nada.

Essa ideia, inclusive, é mais geral: ela funciona para qualquer grafo.

Resumo da solução / implementação:

Vamos implementar um Union-Find com Small to Large, o qual vai manter as componentes, seus poderes, e as posições candidatas (que chegam nessa componente inteira, e poderiam se expandir). Inicialmente, temos que cada componente é uma das posições da matriz.

Em seguida, vamos passar ativando as posições em ordem crescente de poder, unindo a posição aos seus vizinhos ativados. Em uma união, checamos se a componente vizinha tem soma de poderes menor do que o atual, e removemos os candidatos dessa componente caso ela seja; em seguida, unimos o atual a essa componente.

Ao final, os candidatos restantes vão ter resposta igual à soma da matriz inteira.

Para implementar isso, recomendo lidar com as posições como índices em um vetor, ao invés de células em uma matriz.

Clique aqui para conferir o código