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 para compor um dos times. Então, para que haja impasse, devemos ter que , sendo 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 .
- 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 e sua coluna de .
- Se ou ou ou , ou seja, se o próximo quadrado for inválido: seremos jogados para fora da ilha. Retorne -1.
- Incremente em 1.
- Prossiga para a próxima casa.
E essa lógica vai passar, pois cada chamada da função tem complexidade de e chamaremos ela no máximo uma vez para cada quadrado, totalizando .
Clique aqui para conferir o código
Metrônibus
Comentário por Fernando Gonçalves
Subtarefa 1 (31 pontos): = 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á . Caso contrário, a resposta será .
Subtarefa 2 (32 pontos): ≤ 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 .
Então, temos duas formas de implementar isso:
Solução com BFS 0/1
Podemos criar 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 entre os vértices de seu sistema. Adicionamos também arestas de peso 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 , com distância inicial . Dessa forma, a resposta será o mínimo entre as distâncias dos dois sistemas da estação .
A complexidade dessa solução será , pois existem vértices e 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 , 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 .
Então, podemos fazer uma BFS partindo das duas componentes que contém a estação , ambas com peso inicial . Desse modo, a resposta será o mínimo da distância das duas componentes que contém a estação .
A complexidade da união por Union-Find será , pois uniremos duas componentes vezes.
A complexidade da BFS será , pois no grafo temos no máximo vértices e arestas.
Assim, a complexidade dessa solução será .
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 uma permutação de de modo que, quando trocarmos 2 carros no mecânico, temos que , e além disso, a resposta do problema é minima.
Observação: Se e trocamos por , então .
Prova: Vamos olhar para um mecânico . Seja os carros que passaram por ele, nessa ordem. Veja que
- esperou 0 segundos para entrar
- esperou segundos para entrar
- esperou segundos para entrar.
- ...
- esperou segundos para entrar
Então, a somas dos segundos esperados para esse mecânico é , com isso, se com , 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 sempre que .
Com isso, podemos supor que . 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 é , com . Então, vamos tentar criar o algoritmo guloso colocando os carros no . Vamos olhar para o , qual mecânico queremos colocar ele?
Bem, como é 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 carros não contribuirão na resposta, então, seja o primeiro carro em qual colocar ele vai afetar nossa resposta, então, podemos escolher colocar ele no , assim aumentando nossa resposta em , ou então no , assim aumentando em , e assim vai. Veja que, gulosamente o optimal é pegar o tal que é minimo, e assim aumentando nossa resposta em !
Agora, vamos olhar para o . Dá mesma maneira do anterior, gulosamente, é melhor pegar o menor , mas se pegarmos o mesmo em que colocamos o , a nossa resposta vai aumentar em ao invés de só , portanto, só vale a pena pegar esse se ainda for menor que todos os outros . 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 o nosso vetor ordenado em ordem decrescente.
- Passo : Para cada mecânico , seja a quantidade de elementos que já colocamos nele. Então, vemos qual é o mínimo entre , seja ele . Adicionamos a nossa resposta , e aumentamos em 1.
Para calcular esses mínimos, podemos manter esses valores numa priority_queue, e então, a complexidade do problema fica .
Clique aqui para conferir o código