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

Para se preparar para a OBI, confira o nosso Roteiro de Estudos, nele você vai encontrar um direcionamento completo de como estudar!

Para conferir a prova na íntegra, clique aqui.

Troféu

Escrito por Vitor Veiga

Conhecimento prévio necessário:

Dadas cinco pontuações em uma competição, queremos saber o número de competidores empatados com a maior pontuação e com a segunda maior pontuação. Assim, teremos que achar o valor dessas duas pontuações, utilizando um loop, e depois checar quantos participantes obtiveram cada uma delas.

Ordenando o vetor dos valores em ordem decrescente, a primeira posição será o maior número, e o segundo maior será o primeiro número do vetor diferente do maior. Basta agora contar quantas vezes esses valores se repetem utilizando um simples loop, e depois retornar essas quantidades.

Confira o código.

Câmeras

Escrito por Enzo Dantas

Conhecimento prévio necessário:

Busca em grafos

Primeiramente, iremos construir a matriz $N\times{M}$ e marcar quais posições são vigiadas por câmeras e quais estão livres. Se uma câmera posicionada em $(i, j)$ está apontada para o Oeste, por exemplo, vamos marcar todas as posições a direita de $(i, j)$ como vigiadas (todas as posições $(i, k)$ $|$ $j\leq{k}\leq{N}$ ). Em seguida, vamos fazer uma DFS começando do $(1, 1)$ e vamos conferir se a DFS chega na posição $(N, M)$ .

Confira o código

Subcadeias

Escrito por Caique Paiva

Conteúdo Prévio Necessário:

Primeiro perceba que $N$ é bem pequeno, então uma solução $O(N^3)$ passa bem perto do limite. Com um código bem feito, é possivel que passe. Vou fazer uma solução $O(N^2)$ por ser mais rápido.

A parte mais importante do problema são esses dois pontos

Se um intervalo $(l, r)$ é um palindromo, então $(l+1, r-1)$ também é.
Se um intervalo $(l, r)$ não é palindromo, então $(l-1, r+1)$ também não é.

Com isso, vamos fazer o seguinte algoritmo:

Vamos começar com o intervalo $(l, l)$ . Obviamente ele é palindromo.

Passo $i$ : Sabemos que $(l-(i-1), l+(i-1))$ é palindromo. Se $v[l-i] = v[l+i]$ , então $(l-i, l+i)$ é palindromo. Se $v[l-i] \neq v[l+i]$ , então, $(l-i, l+i)$ não é palindromo, e então a gente para o algoritmo, retornando $2i-1$

Roda isso pra todo $l$ de $1$ até $n$ , e sempre salvamos o máximo que esse algoritmo entrega como valor, e então conseguimos o maior palindromo de tamanho ímpar. Para os palíndromos de tamanho par, ao invés de começarmos com $(l, l)$ , basta ver se $v[l] = v[l+1]$ , e se for verdade, rode o algoritmo começando com $(l, l+1)$ .

Código.

Viagem

Escrito por Arthur Lobo

Conhecimento prévio necessário:

Menor Caminho

Nós temos que levar em conta o tempo e o valor, então vamos criar um novo grafo em que os vértices serão representados por um par $(ilha,valor)$ . Queremos saber qual o menor tempo gasto para chegar em cada $ilha$ gastando exatamente $valor$ .

Se existe uma rota da ilha $A$ para $B$ com tempo $T$ e custo $P$ , então no nosso grafo, nós vamos adicionar uma aresta de $(A,val)$ para $(B,val+P)$ com custo $T$ , para todo $0 \leq val \leq V-P$ . Ou seja, se conseguimos chegar em $A$ gastando $val$ em $X$ unidades de tempo, então podemos chegar em $B$ gastando $(val+P)$ em $X+T$ unidades de tempo.

Com esse novo grafo montado, agora basta utilizarmos o algoritmo de Dijkstra nele, ou seja, $dist_{i,val}$ vai guardar o menor tempo possível para chegarmos na ilha $i$ gastando exatamente $val$ . Para isso, começaremos $dist_{1,0} = 0$ e todos os outros com $infinito$ , e agora rodamos Dijkstra normal, com a única diferença que os vértices são identificados por pares de números, e não apenas um número.

É fácil ver que a resposta do problema vai ser $\min_{0\leq val \leq V} (dist_{N,val})$ .

A complexidade final fica $O(N*V*log(N*V))$ , clique aqui para ver o código.