3826. Miojo

Olá meus amigos nerds. Quando se mora sozinho, cozinhar passa a ser um problema, principalmente se você não gosta de jogar comida fora e não tem muito tempo livre (eu que o diga kkk). Uma solução para isso é comer besteiras, tipo miojo. Como somos muito bonzinhos, hoje vamos ajudar o pobre do João a preparar miojos. Já que é isso que o problema 3826. Miojo nos pede para fazer. Mais especificamente, dadas duas ampulhetas (os únicos 'relógios' que ele tem), capazes de medir tempos a e b diferentes e o tempo T necessário para se fazer o miojo, determinar qual será o tempo total gasto para preparar o miojo, incluindo o tempo gasto esperando as ampulhetas estarem em um estado capaz de medir o tempo exato do cozimento do miojo.

Solução

Podemos pensar nesse problema como um problema de decisão. Qual das ampulhetas deve ser virada em seguida para que sejamos capazes de medir exatamente T minutos? Como não podemos inferir a resposta para essa questão, temos que tentar todas as possibilidades e ver qual delas resulta em um menor tempo total.

Os únicos instantes que nos interessam seriam os momentos em que viramos uma ampulheta. Podemos começar virando a ampulheta a, a ampulheta b, ou ambas ao mesmo tempo. Quando uma ampulheta acaba de contar, temos duas opções: (1) vira-la e deixar que ela recomece a contar ou (2) virar as duas ampulhetas, assim a outra ira contar o tempo correspondente a parte da areia que já caiu em seu compartimento inferior. Fazendo-se um backtracking, baseado nessas condições somos capazes de calcular o tempo total.

A condição de parada é que uma das ampulhetas seja capaz de medir exatamente T minutos com a areia remanescente em sua parte superior.

Possivelmente esse problema possui uma solução mais elaborada usando-se teoria dos números (mmc, mdc, etc), mas como a solução por força bruta não é difícil de implementar, resolvi testa-la primeiro e ela se mostrou suficientemente boa para o problema receber um acept.

Implementação

1761. Back to the future

Olá meus amigos nerds. Como a zueira não tem limites, eu não poderia deixar a data de ontem passar em branco. E para isso, nada melhor do que resolver um problema que tem 'de volta para o futuro' no nome e trata de viagens e fluxos. Hoje vamos ajudar nossos amigos a voltar da Alemanha gastando o mínimo possível em passagens aéreas. Já que é isso que o problema 1761. Back to the future nos pede para fazer. (Puts, tinha que ter postado esse problema ontem kkk). Mais especificamente, dadas as rotas aéreas e o número de lugares livres por avião, determinar qual é o mínimo possível que um grupo de d amigos precisa gastar para conseguir viajar entre duas cidades a e b dadas.

Solução

Com um nome desses, esse problema não poderia ser fácil. Como em muitos problemas que envolvem rotas, uma abordagem usando grafos é uma boa ideia. As cidades seriam os vértices de forma que cada vôo seria uma aresta. Cada aresta teria um custo (valor da passagem) e uma capacidade (número de acentos livres). Se você conhece um pouco sobre fluxo máximo em grafos, você deve estar vendo onde quero chegar com essa modelagem.

O problema do fluxo máximo consiste em, encontrar qual seria o maior fluxo, que se poderia transferir de um nó de origem para um nó de destino, respeitando a capacidade de transferir fluxo de cada aresta. Uma analogia seria um sistema hidráulico com canos interligando vários pontos...

Uma variação desse problema é o fluxo máximo a custo mínimo, ou seja, onde cada aresta possui um custo associado, para transportar o fluxo. Como vocês podem observar, nosso problema é praticamente esse.

Fluxo máximo a custo mínimo pode ser resolvido usando-se o algoritmo de Edmonds-Karp. Note que, no problema de fluxo, cada aresta tem duas grandezas associadas a ela, um custo e uma capacidade. A ideia desse algoritmo é ir encontrando caminhos da origem para o destino e transferindo o máximo de fluxo que esse caminho suporta. Mais algoritmicamente: (1) encontre um caminho mínimo (em relação ao custo) da origem ao destino. (2) Verifique qual é a aresta desse caminho que admite a menor capacidade. (3) Transfira, por esse caminho, um fluxo igual a essa capacidade. (4) De cada aresta do caminho subtraia a capacidade transportada. (5) Continue com esse procedimento até que não haja mais caminhos da origem para o destino com todas as arestas com capacidades maiores que 0. Observe que o caminho mínimo muda a cada iteração, pois reduzir a capacidade de uma aresta a 0, corresponde a 'tirar' essa aresta do grafo.

Oras, mas esse problema do fluxo máximo é o mesmo do problema que queríamos resolver, de modo que, o custo do fluxo máximo no grafo dos vôos é a resposta! Errado! Observe que no problema do fluxo máximo assume-se que a origem tem capacidade de produzir um fluxo tão grande quanto o grafo possa aguentar. No nosso caso, o número de passageiros é limitado. Mas se você pensar um pouquinho vai ver que é só parar o algoritmo quando tivermos transportado todos nossos amigos de volta para o Brasil.

Implementação

O problema afirma que nossos amigos tem pouco dinheiro. Mas não deixe se enganar, o custo máximo da viajem de todos pode chegar a 10^15 reais (Imagina eu com esse dinheiro todo, dava até para começar a construir minha própria máquina do tempo :D). Felismente 10^15 cabe em um long long.

O código não está la muito bonito (tempos de maratona, lembra?), me desculpem pelas macros não muito elegantes. Mas também, vocês tem que me dar um desconto, fluxo máximo usa até um dijkstra como uma pequena parte dele.

2608. Duende Perdido

Olá meus amigos nerds. Hoje vamos ajudar um duende a escapar de um complexo de cavernas. Já que é isso que o problema 2608. Duende Perdido nos pede para fazer. Mais especificamente, dado o mapa de um complexo de cavernas, onde estão marcadas as saídas e salões onde o duende não pode visitar, determinar o menor número de salões que o duende tem que passar para poder atingir uma das saídas.

Solução

Podemos resolver esse problema facilmente, se pensarmos nos salões que o duende pode entrar como sendo vértices de um grafo, de modo que os caminhos entre eles sejam as arestas. Assim, a solução do problema seria, simplesmente, computar o caminho mínimo entre a posição atual do duende e uma das saídas. Poderíamos computar o caminho mínimo usando o algoritmo de dijkstra, mas como o tamanho da entrada do problema é pequeno, uma busca em largura é suficiente.

Implementação

8709. Fusões

Olá meus amigos nerds. Hoje vamos verificar se dois códigos bancários pertencem a um mesmo banco ou não. Já que é isso que o problema 8709. Fusões nos pede para fazer. Mais especificamente, dados uma lista de bancos e uma série de fusões entre dois bancos, responder se dois bancos (identificados por seus códigos bancários) são o mesmo banco ou não.

Solução

Esse é um problema fácil. Já resolvemos alguns problemas bem parecidos aqui no blog. O único desafio aqui é fazer união de conjuntos de modo eficiente. Isso pode ser feito usando uma dijoint set forest que implementa tanto a operação de union quanto de find de forma eficiente (O(1)).

Implementação