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