OBI 2017 - Fase 3 - 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.

Para conferir a prova na íntegra, clique aqui.

Taxa

Comentário escrito por Caique Paiva

Conhecimento prévio necessário:

DP em intervalo

Seja $v$ o vetor em que guardamos como vamos dividir o terreno. Vamos fazer uma dp em intervalo para esse problema! Seja dp[ $l$ ][ $r$ ] para ser o menor valor para dividir o terreno em $r-l+1$ intervalos de tamanho $v[l], v[l+1], \cdots, v[r]$ . Então, primeiro veja que $dp[i][i] = 0$ para todo $i$ , e então, a transição vai ser

$dp[i][j] = max(dp[i][k] + dp[k+1][j] + max(sum(i, k), sum(k+1, j))$

Onde $k = i$ e vai até $j-1$ e $sum(i, j)$ é a soma dos vetores de $i$ até $j$ . Veja que todos essas funções (dp e sum) são cíclicas, então por exemplo, se $n = 3$ , então $sum(1, 2) = v[1] + v[2]$ e $sum(2, 1) = v[2] + v[3] + v[1]$ . No final, basta retornar $min(dp[i+1][i])$ para todo $i$ .

Para fazer um vetor circular (como é mostrado no código), a ideia é fazer todas as operações módulo $n$ , ou seja, quando fazemos $i-1$ , se $i$ for ficar negativo, fazemos $(n+i-1) % n$ .

Clique aqui para conferir o código

Postes

Comentário escrito por Enzo Dantas

Conhecimento prévio necessário:

Devemos contar quantos postes devem ser substituídos e quantos devem ser consertados. Para fazer isso, devemos contar quantos postes tem uma altura menor que 50 e quantos tem uma altura entre 50 e 84 (a partir de 85 ele pode ser usado normalmente). Assim, vamos manter dois contadores: $substitui$ e $conserta$ . Ao lermos o input, aumentaremos $substitui$ em 1 toda vez que encontrarmos um número menor que 50 e aumentaremos $conserta$ em 1 toda vez que encontrarmos um número maior ou igual a 50 e menor que 85.

No fim, printaremos $substitui$ e $conserta$ .

Clique aqui para conferir o código

Dividindo o Império

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

Árvores

O problema fala que "Alguns pares de cidades estão ligados diretamente por estradas bidirecionais e, por uma antiga tradição, esses pares são escolhidos de maneira que sempre é possível ir de qualquer cidade para qualquer outra cidade por exatamente um caminho (um caminho é uma sequência de estradas).". Isso quer dizer que o grado do problema é uma árvore.

Então, dado uma árvore, o problema pergunta qual a aresta a ser removida tal que o tamanho das 2 árvores geradas após a remoção seja o mais próximo possível.

A ideia aqui vai ser calcular qual é esse valor para cada aresta e pegarmos o mínimo. Para isso, vamos enraizar a árvore em algum vértice, digamos que seja o vértice 1, e definimos $S_u =$ tamanho da subárvore que tem $u$ como raiz. Exemplo:

Para calcular o valor de $S_u$ , basta perceber que o tamanho da subárvore de $u$ é o somatório do tamanho da subárvore dos filhos $+1$ , então podemos fazer uma $dfs$ em que calculamos primeiro os $S$ dos filhos de $u$ e depois $S_u$ .

Perceba que ao deletarmos a aresta entre qualquer vértice $u \ne 1$ e seu pai, o tamanho das duas árvores resultantes serão $S_u$ e $N-S_u$ , então basta fazermos um for e pegarmos o menor valor de $|S_u-(N-S_u)|$ .

Clique aqui para conferir o código

Arranha-céu

Comentário escrito por Caique Paiva

Conhecimento prévio necessário:

Binary Indexed Tree

Esse problema é uma aplicação simples de BIT. Vamos codar uma BIT de soma, igual a feita na aula colocada no link acima, e nós sabemos que ela responde a query e faz o update em $O(log n)$ . Além disso, vamos guardar o vetor atual, que guarda a quantidade de pessoas em cada apartamento. Na query, retornamos o valor de $query(pos)$ que ele nos dá, e no update, fazemos $update(pos, val - v[pos])$ com o valor e posição que eles no dá na query, e fazemos $v[pos] = val$ .

Clique aqui para conferir o código

Código

Comentário escrito por Arthur Lobo

Conhecimento prévio necessário:

Strings
Set

O problema nos dá uma lista $S_1,S_2,...,S_N$ $strings$ com 10 caracteres cada e nos pergunta se existe qual é a primeira $string$ $S_i$ que é uma $substring$ da contatenação de duas $strings$ $S_a,S_b$ , com $1 \le a,b < i$ , ou dizer que não existe nenhum.

*Para uma string $T$ , vamos definir $T[a:b]$ como sendo a $substring$ $T_{a},T_{a+1},...,T_{b}$ , ou seja, a $substring$ de $a$ até $b$ de $T$ . Além disso, vamos usar 0-indexado, ou seja, a $string$ $T$ inteira é $T[0:T.size()-1]$ .

Parcial 1 ( $N \le 100$ )

Nossa primeira ideia pode ser, para cada $i$ , testar todo par $a,b < i$ e ver se existe alguma $substring$ de $S_aS_b$ igual à $S_i$ . Para cada par, vamos criar uma nova $string$ $T = S_aS_b$ e ver se $T[j:j+9] = S_i$ , para $0 \le j \le 10$ , se algum for, então encontramos o $i$ .

A para cada par $a,b$ , nós checamos em 10 operações (apesar de ser $O(1)$ , 10 é uma constante relativamente alta). Já que existem $O(N^2)$ pares para cada $i$ , e temos $N$ $i$ s, a complexidade final fica $O(N^3)$ , fazendo na verdade ~ $10*N^3$ operações, que é o suficiente para essa subtask.

Parcial 2 (Sem restrições adicionais)

Vamos dar uma olhada em uma representação visual de quando $S_i$ é uma $substring$ de $S_aS_b$ , com as posições correspondentes em $S_i$ e na contatenação sendo iguais.

Basicamente vai existir um $x$ tal que $S_i$ é a contatenação das últimas $x$ posições em $S_a$ e as primeiras $10-x$ posições em $S_b$ .

Para ser mais específico, para que $i$ seja uma $substring$ , deve existir algum $0 \le x \le 10$ tal que

Para algum $a < i$ , $S_i[0:x-1] = S_a[10-x:9]$ (primeiras $x$ posições de $i$ e últimas $x$ de $a$ são iguais).
Para algum $b < i$ , $S_i[x:9] = S_b[0:9-x]$ (últimas $x$ posições de $i$ e primeiras $x$ de $b$ são iguais).

Agora basta guardarmos num set $pre$ todos os prefixos das strings que já passamos, e em $suf$ todos os sufixos das strings que já passamos.

Agora quando estamos em $i$ , basta checarmos se existe algum $x$ tal que $S_i[0:x-1]$ está em $suf$ e $S_i[x:9]$ está em $pre$ . Se existir, então $i$ é a resposta. Por fim, colocamos todos os prefixos de $S_i$ em $pre$ e o mesmo com os sufixos em $suf$ .