OBI 2023 - Fase 3 - Programação Nível Júnior

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 os nossos materiais.

Cabo de Guerra

Comentário escrito por Henrique Vianna

Conhecimento prévio necessário:

Para solucionar esse exercicio, basta checarmos todas as maneiras de separar os 6 integrantes em dois times, cada um com 3 pessoas. Digamos que escolhemos a tripla $(i,j,k)$ para compor um dos times. Então, para que haja impasse, devemos ter que $v[i] + v[j] + v[k] = \frac{\sum{v[i]}}{2}$ , sendo $\sum{v[i]}$ par (caso for ímpar, é automaticante impossível obter-se um impasse). Para isso, basta fazermos três fors, testando essa condição para todas as triplas ordenadas.

Clique aqui para conferir o código

Tesouro

Comentário escrito por João Pedro Castro

Conhecimento prévio necessário:

Busca em Grafos

Começando pelo ponto dado iremos percorrer a ilha seguindo as instruções dadas, e para fazer isso podemos criar uma função que recebe como parâmetro a linha e coluna que estamos e retorna o resultado da busca. A lógica da função é a seguinte:

Se estamos no X: ótimo, chegamos! Retorne o total de passos $P$ .
Se esse quadrado já foi visitado: sabemos que existe um ciclo na ilha, e que nunca sairemos dele, pois já estivemos aqui e voltamos. Retorne 0.
Marque esse quadrado como visitado.
Calcule a próxima casa a ser visitada, chamaremos sua linha de $L_i$ e sua coluna de $C_i$ .
Se $L_i < 1$ ou $L_i > M$ ou $C_i < 1$ ou $C_i > M$ , ou seja, se o próximo quadrado for inválido: seremos jogados para fora da ilha. Retorne -1.
Incremente $P$ em 1.
Prossiga para a próxima casa.

E essa lógica vai passar, pois cada chamada da função tem complexidade de $O(1)$ e chamaremos ela no máximo uma vez para cada quadrado, totalizando $O(M^2)$ .

Clique aqui para conferir o código

Metrônibus

Em breve

Oficina Mecânica

Escrito por Caique Paiva

Conhecimentos prévio necessários:

Para esse problema, uma pessoa pode pensar em vários algoritmos gulosos diferentes, porém a maior parte deles dá errado, então, é importante que você saiba provar que algoritmos funcionam e saber construir exemplos que quebram um algoritmo. Vamos provar uma observação antes de construir o algoritmo. Primeiramente, defina $\{ X_1, X_2, \cdots, X_n \}$ uma permutação de $\{ T_1, T_2, \cdots , T_n \}$ de modo que, quando trocarmos 2 carros $X_i, X_j$ no mecânico, temos que $i < j$ , e além disso, a resposta do problema é minima.

Observação: Se $i < j$ e trocamos $X_i$ por $X_j$ , então $X_i < X_j$ .

Prova: Vamos olhar para um mecânico $M_t$ . Seja $P_1, P_2, \cdots, P_l$ os carros que passaram por ele, nessa ordem. Veja que

$P_1$ esperou 0 segundos para entrar
$P_2$ esperou $P_1M_t$ segundos para entrar
$P_3$ esperou $P_1M_t + P_2M_t$ segundos para entrar.
...
$P_l$ esperou $P_1M_t + P_2M_t + \cdots + P_{l-1}M_t$ segundos para entrar

Então, a somas dos segundos esperados para esse mecânico é $((l-1)P_{1} + (l-2)P_2 + \cdots + P_{l-1})M_t$ , com isso, se $P_i > P_j$ com $i < j$ , então, podemos trocar eles dois de ordem, então conseguimos uma resposta menor, o que é um absurdo, pois essa é a resposta optimal, então $P_i < P_j$ sempre que $i < j$ .

Com isso, podemos supor que $\{ X_1 < X_2 < \cdots < X_n \}$ . Essa observação não é tão importante assim, a parte mais importante é que ela nos mostra a forma da resposta para cada mecânico, que é $((l-1)P_{1} + (l-2)P_2 + \cdots + P_{l-1})M_t$ , com $P_1 < P_2 < \cdots < P_{l-1}$ . Então, vamos tentar criar o algoritmo guloso colocando os carros no . Vamos olhar para o $X_n$ , qual mecânico queremos colocar ele?

Bem, como $X_n$ é maior que todos os outros elementos do vetor, temos que sua contribuição na resposta final vai ser nula, então podemos colocar ele em qualquer mecânico. Sendo mais geral, os últimos $n-m$ carros não contribuirão na resposta, então, seja $X_i$ o primeiro carro em qual colocar ele vai afetar nossa resposta, então, podemos escolher colocar ele no $M_1$ , assim aumentando nossa resposta em $X_iM_1$ , ou então no $M_2$ , assim aumentando em $X_iM_2$ , e assim vai. Veja que, gulosamente o optimal é pegar o $j$ tal que $M_j$ é minimo, e assim aumentando nossa resposta em $M_jX_i$ !

Agora, vamos olhar para o $X_{i-1}$ . Dá mesma maneira do anterior, gulosamente, é melhor pegar o menor $M_k$ , mas se pegarmos o mesmo em que colocamos o $X_i$ , a nossa resposta vai aumentar em $2X_{i-1}M_j$ ao invés de só $X_{i-1}M_j$ , portanto, só vale a pena pegar esse $M_j$ se $2M_j$ ainda for menor que todos os outros $M_k$ . Vendo esses casos bases, é fácil de ver qual vai ser nosso algoritmo guloso.

Primeiro, vamos olhar para o nosso vetor em ordem decrescente. Seja $\{ V_1 > V_2 > \cdots > V_n \}$ o nosso vetor $X$ ordenado em ordem decrescente.

Passo $i$ : Para cada mecânico $M_j$ , seja $C_j$ a quantidade de elementos que já colocamos nele. Então, vemos qual é o mínimo entre $M_jC_j$ , seja ele $M_jC_k$ . Adicionamos a nossa resposta $V_iM_kC_k$ , e aumentamos $C_j$ em 1.

Para calcular esses mínimos, podemos manter esses valores numa priority_queue, e então, a complexidade do problema fica $O(MlogM + N)$ .

Clique aqui para conferir o código