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