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

Para conferir a prova na íntegra, clique aqui.

Cinco

Comentário por Frederico Bulhões

Conhecimento prévio necessário:

String

Para resolvermos essa questão devemos observar uma coisa:

O número inicial dado não é divisível por cinco
Então para que haja resposta é necessário que a troca ocorra entre um número igual a 0 ou 5 e o número da ultima posição, pois então o novo número terminará em 0 ou 5, tornando-o divisível por cinco.

Como $N \leq 1000$ , podemos então fazer um algoritmo em $O(n^2)$ da seguinte forma:

Para todas as posições entre $1$ e $N$ checamos se o dígito daquela posição é 0 ou 5, caso seja, trocamos ele com o último, e comparamos com a resposta computada até agora, caso maior ele se torna a resposta, e depois trocamos de volta o dígito atual com o último.

Na implementação a seguir é usado a função $max$ do C++, que compara lexicograficamente dois vetores passados e retorna o maior.

Clique aqui para conferir o código

Muro

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

Programação Dinâmica

O problema nos pede de quantas maneiras podemos cobrir um grid (matriz) $2\times N$ utilizando dois tipos de tijolos dados. Ele já nos diz a resposta para grids $2\times 0$ , $2\times 1$ e $2\times 2$ , mas como podemos descobrir para um grid maior?

Problemas que perguntam de quantas maneiras conseguirmos cobrir uma matriz $2\times N$ com certos tipos de tijolos geralmente usam programação dinâmica (DP). A ideia normalmente é calcularmos a quantidade de maneiras de preenchermos grids de tamanho até $i-1$ , e usar alguns desses valores para computarmos a quantidade para um grid de tamanho $i$ .

Vamos definir como $dp_i =$ quantidade de maneiras de preenchermos um grid $2\times i$ com os dois tipos de tijolos. Já sabemos os casos base da nossa DP, pois ele nós dá no enunciado: $dp_0 = 1$ , $dp_1 = 1$ , $dp_2 = 5$ . Agora a ideia será encontrar uma recorrência em que $dp_i$ dependa somente de valores menores do que $i$ .

Perceba que qualquer muro de tamanho 3 pode ser "desmembrado" em pedaços independentes de tamanhos $2\times 1$ , $2\times 2$ ou $2\times 3$ . Pedaços independentes significam pedaços que contém apenas peças inteiras dentro e não pode ser mais desmembrado em pedaços independentes menores.

Assim como os muros de tamanho 3, muros de quaisquer tamanho maior que 3 também podem ser desmembrados em mais que dois pedaços independentes de tamanhos $2\times 1$ , $2\times 2$ ou $2\times 3$ , então podemos colocar isso na nossa transição da DP!

A ideia será brutar qual vai ser o final do muro e resolver para um muro menor, sendo que já sabemos quais formatos podem estar no final do muro, então podemos apenas testá-los. Para calcular a $dp_i$ vamos somar:

Existe 1 maneira de fazer com que a parede termine com uma peça independente $2\times1$ , sobrando $2\times i-1$ $\rightarrow 1*dp_{i-1}$ .
Apesar de $dp_2 = 5$ , existem 4 maneiras de fazer com que a parede termine com uma peça independente $2\times 2$ , porque uma das 5 de $dp_2$ possui duas peças independentes, sobrando $2\times i-2$ $\rightarrow 5*dp_{i-2}$ .
Existem 2 maneira de fazer com que a parede termine com uma peça independente $2\times 3$ , sobrando $2\times i-3$ $\rightarrow 2*dp_{i-3}$ .

Podemos "testar" qual dos três finais será, então nossa transição será: $dp_i = 5*dp_{i-1}+1*dp_{i-2}+2*dp{i-3}$ . Agora basta colocar o módulo nisso e conseguiremos calcular a quantidade de maneiras de construir um grid de tamanho $2\times i$ para todo $0 \le i \le N$ módulo $10^9+7$ : $dp_i = (5*dp_{i-1}+1*dp_{i-2}+2*dp{i-3})%(10^9+7)$ .

Clique aqui para conferir o código

Baldes

Escrito por Frederico Bulhões

Conhecimento prévio necessário:

Segtree

Primeiro devemos perceber que para cada balde só importa o menor e o maior valor, e os outros são irrelevantes para a resposta, pois não faz sentido colocar uma bola com o outra de outro balde quando poderíamos pegar uma menor ou maior.

Nesse problema podemos em cada nó da Seg Tree, que representa os baldes entre $L$ e $R$ , guardar três valores:

Valor máximo das bolas entre os baldes $L$ e $R$ , incluso.
Valor mínimo das bola entre os baldes $L$ e $R$ , incluso.
Máximo entre:
- Diferença máxima entre bolas de baldes entre $L$ a $M$ e de baldes entre $M+1$ e $R$ , (sendo $M$ ponto do meio entre $L$ e $R$ );
- Diferença máxima do filho da esquerda, bloco que representa $L$ a $M$
- Diferença máxima do filho da direita, bloco que representa $M+1$ a $R$

Podemos então fazer as queries e updates de acordo com a questão, cada uma em $O(log(N))$ , somando u tempo total de $O(N + Q log(N))$

Clique aqui para ver o código

Recibo de Compra

Escrito por Caique Paiva

Conhecimentos Prévios Necessários:

Vamos fazer uma dp! Os estados serão $(int pos, int pes, int lastn)$ , onde $pos$ é a quantidade de produtos que precisamos pegar, $pes$ é o valor total que precisamos pegar, e $lastn$ o valor do último produto que a gente pegou. Então, a transição da dp vai ser

$dp(pos, pes, lastn) = \sum_{i = 1}^{lastn - 1} dp(pos-1, pes-i, i)$

Veja que, se fizéssemos uma knapsack normal, ou seja, só com os estados $(int pos, int pes)$ e tentassemos aplicar a mesma recorrência, teríamos:

$dp(pos, pes) = \sum_{i = 1}^{lastn-1} dp(pos-1, pes-i)$

Nós retornaríamos com a solução do problema, só que com ordem dos valores importando, ou seja, a escolha de valores $\{1, 4, 7 \}$ seria igual a $\{1, 7, 4\}$ , e além disso, poderíamos ter valores iguais. Por isso, colocamos o estado $lastn$ na dp, pois, além de garantir que não tenha valores iguais na compra, deixa as escolhas dos valores em ordem crescente, e então, não ocorre repetição.

No final, basta retornar $dp(k, r, r+1)$ . Essa dp roda em $O(K R^3)$ , pois temos $O(KR^2)$ estados, e a transição roda em $O(R)$ . Isso passa no problema, visto que $K, R$ são bem pequenos.

Clique aqui para ver o código

Bônus: Um problema parecido com esse é o Coin Combinations do cses, vale a pena dar uma olhada! (Link).

Mancha

Comentário escrito por Frederico Bulhões

Conhecimento prévio necessário:

Para resolver esse problema devemos fazer a seguinte observação:

Caso $d_{manhattan}(x, y) > d(x, y)$ então para algum ponto $z$ na mesma linha ou coluna que o $x$ , é verdade que $d_{manhattan}(x,z) > d(x, z)$ .
Com isso podemos fazer uma busca, em cada linha ou coluna, vendo se existe um buraco nela. Sendo um buraco um quadrado que não faz parte da mancha, mas que para cima e pra baixo, ou pra esquerda e direita, tenha algum ponto que faz parte da mancha. Pois a distância entre esses pontos, será maior que a distância de manhattan, pois teremos que dar uma volta.

Então podemos escrever uma solução em $O(n^2)$ para resolver esse problema, passando por cada linha e cada coluna checando essa condição em $O(n)$ .

Nessa implementação checamosse a soma de pontos que são da mancha entre o primeiro e ultimo daquela linha/coluna é igual a distância entre o primeiro e o último. Caso sim para toadas as linhas e colunas a resposta é sim. Senão a resposta é não.

Clique aqui para conferir o código

Bolas

Comentário escrito por Frederico Bulhões

Conhecimento prévio necessário

Princípio da casa dos pombos

Para resolver esse problema podemos usar o Pricípio da Casa dos Pombos. Caso tenhamos um valor com mais de 4 ocorrências, então obrigatoriamente vamos ter que colocar uma dessas bola do lado da outra igual. Para resolver esse problema basta checar essa condição, pois caso ela ocorra, só pode ocorrer com uma bola de um valor.

O código resultante tem complexidade de $O(1)$ .