OBI 2023 - Fase 3 - Programação Nível 1

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

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:

Busca em grafos

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:

Vértices Auxiliares
BFS 0/1 ou Union-Find e BFS

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

Dominó Nlogônico

Comentário por Henrique Vianna

Conhecimento prévio necessário:

Explorando a STL - Stack

Nesse exercicio, dada uma lista de $N$ dominós, deve-se computar para cada um quantos outros dominós ele derruba, seja diretamente ou indiretamente. Um dominó $i$ atinge um outro dominó $j$ de forma direta se, e somente se, $i > j$ e $x[i] + h[i] \geq x[j]$ .

Intuitivamente, faz sentido calcularmos as respostas para cada um dos dominós em ordem decrescente (de $N$ a $1$ ), uma vez que um dado dominó só pode afetar aqueles que estão para a sua direita. Para nos auxiliar nessa tarefa, faremos uso de uma stack chamada de ativos, que guardará os índices dos dominós ainda não derrubados. Ademais, seja $f[i]$ o número de dominós que o dominó $i$ derruba. Então, tendo já calculado $f[j]$ para $j > i$ e mantendo essa stack, basta fazermos:

$f[i] = 1 + \sum_{j \in ativos}f[j]$ , se $x[i] + h[i] \geq x[j]$ .

Perceba que se o dominó atual derrubar um dado dominó $j$ de ativos, então deve-se remover $j$ da stack. Ao acabarmos de processarmos o dominó $i$ , devemos inseri-lo em ativos e avançar para o dominó $i - 1$ . Perceba que, uma vez que inserimos e retiramos um dado dominó da nossa stack uma única vez, a complexidade de nosso algoritmo é Ao final, basta imprimirmos $f[i]$ para $1 \leq i \leq N$ .

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.