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

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:

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

Comentário por Fernando Gonçalves

Subtarefa 1 (31 pontos): K_2 = 0, ou seja, todas as ligações são do sistema de metrô.

Conhecimento prévio:

Para essa parcial, sabemos que só existe o sistema de metrô. Portanto, precisamos apenas checar se é possível ir da estação inicial para a estação final pelas ligações.

Podemos fazer isso com um algoritmo qualquer de busca em grafos.

Se for possível chegar na estação final, a resposta será P. Caso contrário, a resposta será -1.

Subtarefa 2 (32 pontos): N ≤ 100.

Essa parcial é resolvida usando a ideia principal do problema (que será explicada mais adiante) porém com algum algoritmo ineficiente.

Subtarefa 3 (37 pontos): Nenhuma restrição adicional

Conhecimento prévio:

A ideia principal do problema é que podemos separar cada vértice em dois outros: o vértice no qual estou usando o sistema de metrô e o vértice no qual estou usando o sistema de ônibus.

Com isso, sabemos que cada ligação do sistema de metrô ligará duas estações que estão usando o metrô. De forma análoga, cada ligação do sistema de ônibus ligará duas estações que estão usando o ônibus. Por fim, em cada estação é possível mudar o sistema que está sendo usado, com custo P.

Então, temos duas formas de implementar isso:

Solução com BFS 0/1

Podemos criar 2N vértices, os quais indicarão, para cada estação, qual o sistema que está sendo utilizado. A seguir, adicionamos, para cada ligação, uma aresta de peso 0 entre os vértices de seu sistema. Adicionamos também arestas de peso P entre os vértices que indicam diferentes sistemas da mesma estação.

Fazemos então uma BFS 0/1 que parte dos dois sistemas da estação A, com distância inicial P. Dessa forma, a resposta será o mínimo entre as distâncias dos dois sistemas da estação B.

A complexidade dessa solução será O(N + K_1 + K_2), pois existem 2N vértices e K_1 + K_2 arestas no grafo.

Clique aqui para conferir o código

Solução com Union-Find e BFS

Note que, a partir de uma estação que está usando um sistema específico, é possível alcançar todas as estações que estão conectadas por esse sistema com um mesmo custo. Assim, para toda a ligação, podemos unir com um Union-Find as duas estações daquele sistema, já que o custo das duas será o mesmo.

Desta forma, criaremos diversas componentes de estações que têm um mesmo custo.

Essas componentes serão ligadas entre si por arestas de peso P, que ligarão os dois sistemas de uma mesma estação.

Portanto, as componentes formarão um grafo que contém apenas arestas de peso P.

Então, podemos fazer uma BFS partindo das duas componentes que contém a estação A, ambas com peso inicial P. Desse modo, a resposta será o mínimo da distância das duas componentes que contém a estação B.

A complexidade da união por Union-Find será O(K_1 + K_2), pois uniremos duas componentes K_1 + K_2 vezes.

A complexidade da BFS será O(N), pois no grafo temos no máximo 2N vértices e N arestas.

Assim, a complexidade dessa solução será O(N + K_1 + K_2).

Clique aqui para conferir o código

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