1751. A lei vai a Cavalo!

Olá meus amigos nerds. Hoje vamos ajudar a polícia canadense a decidir o número máximo de policiais que podem ter um cavalo para montar. Já que é isso que o problema 1751. A lei vai a Cavalo! nos pede para fazer. Mais especificamente, dadas as afinidades entre cavalos e cavaleiros; e o número de cavaleiros que podem montar cada cavalo, determinar o número máximo de policiais que podem ter um cavalo para montar em uma atribuição entre cavalos e cavaleiro.

Solução

Esse problema envolve uma atribuição (match) entre cavalos e cavaleiros, uma boa forma de modelar a solução de problemas assim é usando grafos. Considere o grafo bipartido onde os vértices representam os cavalos e cavaleiros. Sendo que existe uma aresta entre dois vértices se o cavalo é compatível com o cavaleiro. Além disso, a cada vértice que representa um cavalo vou atribuir uma capacidade c igual ao número de cavaleiros que podem montar esse cavalo. Do mesmo modo, para cada vértice que representa um cavaleiro vou atribuir uma capacidade (igual a 1, já que cada cavaleiro pode montar apenas 1 cavalo).

O número máximo de cavaleiros que poderiam ter um cavalo para montar pode ser calculado como o fluxo máximo que pode passar por esse grafo, considerando-se os cavaleiros como sources e os cavalos como sinks. A ideia por traz disso está no fato de que: a escolha de uma aresta para a passagem do fluxo corresponde a um match entre cavalo e cavaleiro, sendo assim com o fluxo máximo representa o número máximo de arestas que eu consigo usar (cada aresta tem capacidade 1) para atribuir um cavaleiro a um cavalo.

Para usarmos o algoritmo clássico (Ford–Fulkerson) de fluxo máximo, nosso grafo tem que ter apenas um source e um sink. Para transformar um grafo com múltiplos sources em um grafo com apenas um, basta incluir um vértice extra no grafo e liga-lo a cada source, sendo que cada aresta adicionada tem um peso igual a capacidade do vértice (source). Analogamente, podemos usar essa mesma técnica para reduzir o número de sinks para um.

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

1368. Orkut

Olá meus amigos nerds. Hoje vamos voltar no tempo e ajudar nossa amiga Larissa a adicionar seus amigos no Orkut (muitas recordações? kkk). Já que é isso que o problema 1368. Orkut nos pede para fazer. Mais especificamente, dados os amigos de Larissa e as restrições que eles impõe a ela (na forma de quais outros usuários ela deve ser amiga), para aceitarem seu convite, determine a ordem em que ela deve adiciona-los de modo que todos a aceitem.

Solução

Esse problema implora que usemos grafos para modela-lo (grande novidade, já que eu adoro grafos kkk). Onde os vértices representam os amigos de Larissa e existe uma aresta de a para b se b exige que Larissa seja amiga de a para aceitar seu convite. Observe que esse grafo representa as dependências para que um amigo aceite Larissa.

Em teoria de grafos, existe o conceito de ordenação topológica, que é uma ordenação dos vértices de um grafo de modo que se existe uma aresta ab então  a deve vir antes de b nessa ordenação. Em outras palavras, se enxergarmos as arestas como dependências, todos os vértices que dependem de um vértice (têm uma aresta os ligando) devem vir após ele na ordenação. Oras, mas isso é exatamente o que queremos.

Assim a resposta para o problema é ordenar topologicamente o grafo. Note que pela definição de ordenação topológica o grafo deve ser acíclico, caso contrário seria impossível existir uma ordenação válida. Note ainda, que existem várias ordenações possíveis, basta permutar vértices que não dependem de ninguém em uma ordenação válida, que você obtém outra ordenação válida diferente.

Existem dois algoritmos, relativamente simples, para se obter uma ordenação topológica. Você pode encontrar uma explicação mais detalhada sobre eles aqui. Vou descrever, em linhas gerais, um deles que eu usei para resolver esse problema.

Suponha que o grafo é acíclico. A ideia é fazer uma busca em profundidade começando de algum vértice não visitado ainda. Nessa busca, as dependências de um dado vértice são visitadas depois de ele ter sido visitado. Então se eu escrever os vértices na ordem contrária que eles são visitados isso constituirá em uma ordenação válida.

Implementação

Observe que eu primeiramente verifico se o grafo é acíclico. Isso não seria necessário se eu implementasse com um pouco mais de cuidado a ordenação topológica, mas para os fim desse problema acho que isso é suficiente.

1332. Dengue

Olá meus amigos nerds. Hoje vamos ajudar o povo da Costa do Mosquito a instalar um posto de vacinação. Já que é isso que o problema 1332. Dengue nos pede para fazer. Mais especificamente, dado um conjunto de cidades e as rotas que as ligam, determinar em qual cidade deve ser instalado o posto de vacinação de modo a minimizar a distância percorrida por quem mora mais longe do posto.

Solução

Esse problema implora que usemos grafos para modela-lo. As cidades são os vértices e as rodovias as arestas. Como a entrada do problema é bem pequena, basta então calcular a distância entre todas as cidades e escolher a cidade que tem a menor distância máxima. Para calcular a distância de uma cidade para todas as outras podemos usar o algoritmo de dijkstra. Facinho né!

Implementação

11016. Reduzindo detalhes em um mapa

Reuso de código é algo muito desejável em engenharia de software. Muitos pensam que isso não é muito comum em maratonas  de programação, mas na verdade tem uma bibliotéca com os algoritmos clássicos implementados ajuda muito.

Hoje aconteceu algo muito engraçado! Como sempre, eu peguei um problema aleatoriamente no spoj e fui resolver (o problema do post anterior :P). Levei pouquissimo tempo para encontrar a solução e quando já tinha a modelagem sabia que precisaria implementar o algoritmo de Kruskal. Eu já havia implementado ele outras vezes. Como é um algoritmo mais longo eu estava com preguiça de fazer isso de novo, então resolvi dar um grep no diretório onde guardo os problemas que já fiz e encontrei tal algoritmo para solucionar o problema 11016. Reduzindo detalhes em um mapa. Até ai tudo normal, mas a coisa engraçada é que o mesmo código (incluindo a parte de entrada e saída) resolvia o problema anterior, ou seja, reuso de código é para os fracos, bom mesmo é reuso de toda a implementação kkk.

Mas especificamente, esse problema pede que dado um mapa de cidades e rodovias que as ligam, selecione um subconjunto das rodovias tal que entre qualquer par de cidades exista uma rota ligando-as e a soma dos comprimentos das rodovias é mínimo.

Solução

Como o problema da árvore geradora mínima e o algoritmo de Kruskal estão fresquinhos em sua cabeça você deve achar esse problema moleza (se não estiverem isso pode ajudá-lo). Não é difícil perceber que o sub conjunto de rodovias pedido é uma árvore. Caso não fosse, ou seja, houvesse algum ciclo no grafo, poderíamos remover a rodovia com maior comprimento o que não causaria a perda da conectividade entre as cidades (sobra o outro caminho) e ainda diminuiria o comprimento total.

Logo a sulução do problema é soma dos pesos da árvore geredora mínima formada.

Implementação

12999. Frete da Família Silva

Olá meus amigos nerds. Hoje vamos ajudar a família Silva a comemorar sua chegada a Marte. Já que é isso que o problema 12999. Frete da Família Silva nos pede para fazer.

Tenho que cumprimentar muito o autor desse problema, ele conseguiu ser extremamente criativo. O problema em si é interessante e o cara fez uma contextualização muito engraçada usando elementos do Chapolim Colorado. Vale até o quote:

"O presidente de Pizzalândia, Lagosta da Silva, ... Resolveu, então, mandar uma família inteira para Marte. No caso, a dele mesmo, a família Silva, provavelmente a mais numerosa do planeta.

Tal família estabeleceu-se em Marte sem problemas, ainda mais com novas invenções que havia por lá. Uma delas era a pílula de nanicolina, substância descoberta naquele planeta, próximo à uma região onde existem pedras voadoras, pedras macias e até pedras falantes. Lendas dizem que algum outro ser extra-terrestre depositou a nanicolina ali num passado distante, enquanto visitava o planeta. O efeito da pílula de nanicolina é a diminuição de tamanho de quem a toma, por um determinado tempo. Tal pílula foi, então, produzida em escala industrial e hoje em dia é distribuída pelos governos marcianos aos colonos que lá residem."

Mas deixando a brincadeira de lado. Mais especificamente, nossa tarefa é determinar o valor mínimo gasto por senhor Lagosta para fazer com que todos os parentes se encontrem.

Solução

Esse é claramente um problema que pede uma modelagem utilizando grafos (colônias = vértices, caminhos = arestas). Além disso, estamos lidando com um grafo ponderado (as 'estradas' tem peso) e conexo, já que sempre existe um caminho entre quaisquer duas colônias.

A primeira coisa a perceber  é que, dada um par de cidades, devemos usar o caminho mínimo entre essas cidades para deslocar todos os colonos de uma cidade para a outra.

Como a capacidade dos ônibus é inimitada, nessa viagem podemos aproveitar para levar todos os colonos que estão nos outro vértices do caminho mínimo,  já que esse também será o caminho mínimo para eles. Disso deduzimos que nenhuma estrada será usada mais que uma vez.

Do paragrafo anterior, também podemos concluir que o sub grafo formado pelos caminhos de todos os colonos até o ponto de encontro é uma árvore. Caso houvesse um ciclo poderíamos retirar a aresta de maior peso desse ciclo e usar o outro caminho restante para levar as pessoas que estavam nos vértices que a aresta foi removida.

Logo a solução para nosso problema é a árvore que tenha o menor custo (i. e. a soma dos pesos das arestas). Esse é um problema bastante famoso em computação chamado problema da árvore geradora mínima e pode ser resolvido utilizando o algoritmo de Kruskal.

O algoritmo de Kruskal, basicamente, ordena as arestas e depois itera sobre a lista ordenada escolhendo de forma gulosa as arestas que fazem parte da árvore. Assim, a complexidade dele é O(num_arestas*log(num_arestas) + num+arestas) = O(num_arestas*log(num_arestas)). Obs: a operação dsf_union tem custo amortizado O(1). Ela é parte da implementação de um conjunto disjunto, um algoritmo capaz  de fazer find e union entre conjuntos de forma eficiente.

Implementação

Veja que, a implementação do algoritmo de Kruskal não é muito complicada. De quebra ainda ganhamos a implementação de um conjunto disjunto de árvores para uso futuro :)

844. Número de Erdos

Olá meus amigos nerds. Hoje vamos resolver um dos primeiros problemas que me apresentaram a essa vida de resolver problemas. Vamos tentar descobrir qual é nosso número de Erdos, já que é isso que o problema 844. Número de Erdos nos pede para fazer. Mais especificamente, nossa tarefa é determinar, a partir de uma lista de autores de artigos, o número de Erdos dos autores.

Nesse problema, vale a pena até contar mais um pouco de história. O matemático húngaro Paul Erdos (1913-1996), é considerado o matemático mais prolífico da história, devido ao seu alto número de publicações (mais de 1500). Em homenagem a este gênio húngaro, os matemáticos criaram um número, denominado "número de Erdos". Toda pessoa que escreveu um artigo com Erdos tem o número 1. Todos que não possuem número 1, mas escreveram algum artigo juntamente com alguém que possui número 1, possuem número 2. E assim por diante. Quando nenhuma ligação pode ser estabelecida entre Erdos e uma pessoa, diz-se que esta possui número de Erdos infinito. Por exemplo, o número de Erdos de Albert Einstein é 2. E, talvez surpreendentemente, o número de Erdos de Bill Gates é 4.

Solução

Outro problema que a solução é uma busca em largura! Mas por motivos históricos, não resisti a tentação de escrever ele. Dado um grafo onde os vértices representam os autores e existe uma aresta entre dois vértices se os autores publicaram juntos, o tamanho do caminho mínimo entre o cada vértice e o vértice que representa Erdos é o número procurado. Como todas as arestas tem o mesmo peso (o grafo não é ponderado), uma simples busca em largura resolve.

Implementação

Que código feio, mas vocês tem que me perdoar já que ele foi escrito há muitos anos atrás.

819. Pedágio

Olá meus amigos nerds, hoje vamos ajudar Juquinha a decidir quais cidades ele pode visitar. Já que é isso que o problema 819. Pedágio nos pede para fazer. Mais especificamente, dado um mapa com as cidades e estradas, determinar quais cidades são alcançáveis a partir da cidade em que Juquinha se encontra e que o caminho até elas necessite que sejam pagos no máximo P pedágios.

Solução

O problema quase que implora por uma solução usando-se grafos, onde os vértices representam cidades e as arestas rodovias entre elas. Neste grafo o peso de uma aresta representa o custo do pedágio. Assim sendo o problema se reduz ao cálculo do caminho mínimo entre o vértice que representa a cidade onde Juquinha está e todos os outros vértices do grafo.

O caminho mínimo pode ser calculado facilmente usando-se o algoritmo de dijkstra. Hoje estou com pouco tempo, mas outro dia eu ainda quero discutir mais esse, que é um algoritmo muito clássico.

Assim sendo, para resolver o problema basta calcular o caminho mínimo e a resposta será o conjunto de cidades que estão a menos de P pedágios de distância.

P.S. como todos os pesos das arestas são iguais a 1 eu poderia ter simplesmente feito uma busca em largura para calcular a distância, mas resolvi usar dijkstra para deixar a explicação da solução mais simples :).

Implementação

P.S. Não reparem a feiura do código, mas é que eu resolvi esse problema faz muitos anos e fiquei com preguiça de deixar o código mais bonitinho. Pelo menos, observem que realmente melhoramos quando brincamos continuamente de resolver problemas kkk.

11651. Banda

Olá meus amigos nerds, esquentem seus motores, pois hoje começa o code jam 2015 e é claro que vocês não vão querer perder essa.  E para começar bem o dia, nada melhor do que resolvermos um probleminha, não é mesmo?

Hoje vamos ajudar o Jimmy a montar sua banda, já que é isso que o problema 11651. Banda nos pede para fazer. Mais expecificamente, dada uma lista de músicos e suas respectivas afinidades e deseja-se escolher três dentre esses músicos de modo a maximizar a afinidade deles.

Solução

O problema é bem simples. Podemos modelar os músicos como sendo vértices de um grafo, desse modo as arestas do grafo representariam a afinidade entre o par de músicos representados pelos vértices. Agora basta percorrermos esse grafo e encontrarmos a trinca de músicos com a maior soma das afinidades. O seguinte algoritmo faz isso:

maxScore = -1

for i in vertices_grafo

    for j in vertices_adjacentes[i]

        for k in vertices_adjacentes[j]

            score = afinidade[i][j] + afinidade[i][k] + afinidade[j][k]

            if score > maxScore

                maxScore = score

                trio = (i, j, k)

O algoritmo acima é O(n^3), onde n é o número de vértices, mas como a entrada é pequena esse algoritmo é suficiente para resolver o problema e passar no tempo.

Implementação

1353. Festa Junina

Olá meus amigos nerds, hoje vamos ajudar o diretor de uma escola a montar uma comissão para realização de sua tradicional festa junina, já que é isso que o problema 1353. Festa Junina nos pede para fazer.

Mais especificamente, dada uma lista de alunos e as relações de ódio entre eles (que triste rsrs), determinar qual é o número máximo de integrantes que a comissão da festa pode ter, se ela for formada pelos alunos da lista.

Solução

Esse é um problema bastante interessante. Uma solução baseada em testar todos os conjuntos de alunos possíveis é bem fácil de ser pensada, entretanto apresenta o problema de o número de partições de um conjunto ser exponencial (2^n). Tentemos então encontrar soluções melhores!

Vamos resolver esse problema usando uma modelagem por grafos. Cada vértice do grafo representa um aluno da lista. Existe uma aresta entre dois vértices, caso um dos alunos que aqueles vértices representam odeio o outro. Em outras palavras, esse grafo representa as relações de ódio entre os alunos. Observe que para uma comissão ser válida não podem haver arestas no grafo que liguem os membros da comissão, ou seja, as comissões válidas são os conjuntos independentes existentes no grafo. Logo o problema se resume a achar o conjunto independente máximo do grafo.

Achar o conjunto independente máximo é o problema dual de achar a clique máxima (um conjunto independente é uma clique (sub grafo completo) no grafo complementar). Mas por que eu estou falando isso? Se você já estudou um pouco de teoria de complexidade, você já deve ter ouvido falar que o problema da clique máxima é NP-completo. Sendo assim, estamos diante de um problema que a melhor solução que conhecemos tem complexidade exponencial.

Assim a ideia que mencionei no primeiro parágrafo apesar de ineficiente é ótima. Observando que o tamanho máximo da entrada é 20 mesmo uma solução assim é capaz de passar no tempo no spoj. O seguinte algoritmo implementa tal ideia:

construa o grafo de relações de odio entre os alunos
tamanhoMaximoGrupo = 0
para cada conjunto de alunos
   Seja S esse conjunto
   para cada a em S
     para cada b em S
        se existe a aresta a->b ou b->a no grafo
          conjunto invalido
   tamanhoMaximoGrupo = max(tamanhoMaximoGrupo, |S|)

Implementação

A solução abaixo utiliza um backtracking para implementar o algoritmo acima. Ela é basicamente, um algoritmo de enumeração de conjuntos.

Uma ideia um pouco mais elaborada é utilizar um bitset para representar os conjuntos. A implementação abaixo é baseada nisso. A ideia é iterar de 1 a 2^n e utilizando a representação binária do iterador como a representação do conjunto. Embora um pouco mais eficiente ela também é mais propícia a erros, já que operações com bits as vezes são traiçoeiras.

3776. Árvore Genealógica

Olá meus amigos nerds, passado o ano novo é hora de retomarmos nossa rotina de resolver problemas. E para vocês não dizerem que sou um cara mau, irei começar o ano com um problema fácil, porém interessante.

Hoje vamos resolver o problema 3776. Árvore Genealógica, que nos pede para, dada uma árvore genealógica, dizer quem são os parentes mais distantes.

Primeiramente, gostaria de dizer que esse problema é muito semelhante ao 11011. Desafio cartográfico, que foi o primeiro problema resolvido nesse blog. Seria isso uma coincidência de inicio de ano?

Solução

O problema define o grau de parentesco da seguinte maneira:

grau(A, B) = 0, se A = B
grau(A, B) = 1 + min(grau(pai(A), B), grau(A, pai(B))), se A != B

A recursão acima, e o fato de se tratar de uma árvore genealógica, praticamente nos implora para que modelemos esse problema utilizando grafos, onde os vértices são as pessoas e as arestas são uma relação direta de parentesco. 

Se pensarmos bem, a recursão acima nos conta que os dois parentes mais distantes são aqueles que fazem parte das extremidades do diamêtro da árvore. Isso nos conduziria a uma solução muito semelhante a do problema 11011, ou seja duas buscas em profundidade, sendo a segunda feita a partir do vértice mais distante da raiz da primeira busca.

Entretanto, é interessante notar, que o tamanho máximo da entrada é pequeno (1000) o que nos faz pensar que uma solução um pouco menos elaborada (mais força bruta) seja suficiente para resolver o problema. Bem e qual seria essa solução? Hora, para cada par A, B de pessoas calcular seu grau de parentesco e imprimir aquelas que tem o maior grau. Algoritmicamente falando:

Seja pessoas o conjunto de todos os vértices da árvore

maiorGrau = 0

for A in pessoas

  for B in pessoas

    g = grau(A, B)

    maiorGrau = max(g, maiorGrau)

Onde grau(A,B) é descrito pela recursão citada no início do problema. Observe que no caso médio a complexidade de grau(a,b) é logarítmica (altura da árvore), sendo assim meu algoritmo de força bruta tem complexidade de O(n² * log(n)) sendo n o número de pessoas. E isso é bom o suficiente para resolver esse problema. 

Observe, que caso quiséssemos modelar o problema como o diâmetro do grafo, teríamos que tratar o fato de a entrada poder ser uma floresta de árvores (um grafo desconexo). Problema que não existe no caso de uma solução por força bruta. Isso mostra a importância de entendermos os compromissos entre simplicidade e viabilidade (em ralação aos limites de entrada) de nossas soluções.

Implementação

Observem, como eu represento a floresta de árvores como um vetor, armazenando apenas o antecessor de cada nó.

Observem, também, que mesmo minha implementação tendo uma complexidade O(n³) no pior caso, ela ainda assim é aceita no spoj.

1824. Monitorando a Amazônia

Olá meus amigos nerds, vocês acharam que essa semana não ia ter um probleminha? Se sim, se enganaram! Eu queria ter postado esse probleminha na quarta, mas vocês hão de convir comigo que seria uma pena perder os jogos dos dois melhores times do Brasil da atualidade... Deixando de papo furado, que a diversão comece!

Hoje vamos resolver o problema 1824. Monitorando a Amazônia, que nos pede para verificar se é possível enviar uma mensagem de uma estação de comunicação central para todas as outras estações de comunicação espalhadas pela amazônia. Sendo que, cada estação se comunica apenas com as duas estações mais próximas a ela.

Solução

Conceitualmente esse não é um problema difícil. Se pensarmos a rede de comunicação como sendo um grafo (direcionado), basta verificarmos se todos os vértices são alcançáveis, a partir do vértice que representa a estação central. Isso pode ser feito, facilmente, usando-se uma busca em profundidade. 

Note que, o problema pede apenas para verificar se é possível enviar uma mensagem a partir da estação central. Caso se pedisse para verificar a viabilidade da comunicação entre qualquer par de estações, o problema seria um pouco mais complexo. Nesse caso teríamos que verificar se o grafo possuía apenas um componente fortemente conectado, o que poderia ser feito usando-se o algoritmo de Tarjan.

O seguinte algoritmo resolve o problema

calcule a distância entre cada par de estações
Seja G um grafo onde os vértices representam as estações
para cada estação
    Sejam a e b as estações mais próximas a est
    adicione a aresta est -> a a G
    adicione a aresta est -> b a G
faça uma busca em profundidade a partir do vértice que representa a estação principal marcando todos os vertices visitados
if todos os vértices foram marcados
    print "All stations are reachable."
else
    print "There are stations that are unreachable."

Implementação

Observe que evitamos o uso de números de ponto flutuante trabalhando com o quadrado da distância. Em alguns problemas isso pode ser bem útil.

Observe ainda, que abrimos mão de alguma elegância no código em favor de não armazenar as distâncias entre cada par de estações. Sendo assim vou aproveitar e deixar um pequeno desafio para você: o código abaixo contém 2 bugs, quanto tempo você levaria para encontrá-los?

Obs: Caso você tenha dificuldade em encontrar os bugs use o diff :)

1737. Mesa da Sra Montagny!

Olá meus amigos nerds, enquanto alguém não inventar um remédio mágico para garganta inflamada (minha garganta agradeceria) vamos resolver mais problemas.

O problema de hoje é o 1737. Mesa da Sra Montagny! e nele vamos ajudar a sra Montagny a decidir se é possível dispor todos os seus convidados numa mesa de forma que cada convidado tenha todos os seus amigos no lado oposto da mesa.

Solução

Como não vejo a hora de me deitar para descansar vou resolver problema de forma bem rápida. O problema nos fornece as relações de amizade dos convidados, isso sugere fortemente que a utilização de grafos é uma boa ideia para o problema.

Para que seja possível dispor os convidados, não pode haver um convidado que possua amigos dos dois lados da mesa. Se pensarmos os lados da mesa como conjuntos de vértices, qual tipo de grafo tem essa propriedade? Grafos bipartidos. Então o problema nos pede para identificar se o grafo é bipartido. Caso o grafo formado pelas relações de amizade seja bipartido, a sra Montagny poderá dispor seus convidados na mesa, caso contrário não.

Identificar se um grafo é bipartido é fácil. Basta fazer uma busca em profundidade, marcando os vértices de um dos conjuntos de uma cor e os do outro conjunto com outra. Caso eu encontre um vértice que deveria ter uma cor mas ele tem outra então o grafo não é bipartido, caso contrário ele é.

P.S. prometo que semana que vem falo de um problema mais interessante, mas hoje minha garganta me pede para fazer outras coisas rsrs

Implementação

2616. Caixeiro-Viajante B

Olá meus amigos nerds, mesmo estando com um pouco de calos nos olhos devido ao jogo de ontem da seleção, estou aqui hoje para resolver um probleminha com vocês.

Hoje vamos falar do problema 2616. Caixeiro-Viajante B que nos pede para traçar a rota de um caixeiro viajante de modo que ele gaste o mínimo possível com passagens de trem para visitar todos os seus clientes. Mais especificamente, o problema só nos pede o valor mínimo gasto com as passagens.

Solução

O primeiro ponto a destacar, é que esse não é o clássico problema do caixeiro viajante, tão estudado quando se fala em problemas NP. Ainda bem, já que isso facilita bastante as coisas.

Como em outros problemas que já resolvemos aqui, vamos pensar em uma modelagem usando grafos. Nesse problema isso é bem simples, as cidades seriam os vértices e as ferrovias as arestas.

O problema nos afirma que há apenas um caminho ligando cada par de cidades, então nosso grafo é, na realidade, uma árvore. Cada cidade em que há um cliente do caixeiro precisa ser visitada, isso significa que cada ferrovia que o caixeiro passar será usada 2 vezes (ida e volta).

A forma de minimizar o gasto com passagens é não percorrer uma ferrovia mais do que uma duas vez (ida e volta), já que há apenas 1 caminho entre qualquer par de cidades. Isso significa que, cada vez que o caixeiro chegar a uma "encruzilhada" que tem caminhos para mais do que uma cidade ele deve visitar a primeira delas, voltar até a encruzilhada e partir dali direto para a próxima cidade. Observe que o que acabei de descrever é simplesmente percorrer o grafo em uma busca em profundidade.

Problema resolvido? Não! Pode haver cidades que não possuem clientes do caixeiro e que não estão no caminho de outras cidades, ou seja, que não precisam ser visitadas, mas que provavelmente seriam contadas caso você fizesse uma busca em profundidade simples. Mas isso é simples de resolver. Para contornar esse pequeno detalhe basta fazer a busca em profundidade primeiro (enraizando a árvore pelo nó que representa a cidade inicial do caixeiro) e ir percorrendo os caminhos das cidades de destino para a raiz (ou seja, fazendo o caminho oposto), marcando as arestas para que elas não sejam contadas novamente.

Implementação

818. Aeroporto

Olá meus amigos nerds, depois de algumas decepções na última semana, nada melhor que afogar as mágoas resolvendo alguns problemas! E hoje eu trago um problema simples para vocês.

A crescente utilização do transporte aéreo preocupa os especialistas, que prevêem que o congestionamento em aeroportos poderá se tornar um grande problema no futuro. Pensando nisso, o problema 818. Aeroporto nos pede para determinar, a partir de uma listagem de aeroportos e vôos, qual aeroporto possui maior probabilidade de congestionamento no futuro. Como medida da probabilidade de congestionamento o problema usa a soma do número de vôos que chegam e que partem de cada aeroporto. Mais especificamente, o problema pede o identificador do aeroporto que possui maior tráfego aéreo, onde o tráfego é medido pela soma do número de vôos que chegam e que partem do aeroporto.

Modelagem

A simples leitura do problema sugere uma modelagem por grafos. Podemos representar cada aeroporto por um vértice no nosso grafo, assim cada aresta representará um vôo de um aeroporto para outro. Nessa modelagem, o tráfego de cada aeroporto corresponde ao grau do vértice que representa aquele aeroporto. Assim, a resposta para nosso problema é o maior grau dos vértices de nosso grafo.

Computar o grau de cada vértice é bastante simples:

para cada aresta (v1->v2) do grafo

    grau_saída[v1]++

    grau_entrada[v2]++

Observe que o algoritmo acima funciona mesmo que o grafo tenha arestas paralelas (o que pode ser o caso em nosso problema).

Logo o tráfego em cada aeroporto A será:

trafego[A] = grau_saída[A] + grau_entrada[A]

Assim a resposta do problema será o maior elemento do vetor trafego.

Implementação

1331. Dominó

Olá, hoje vamos comemorar a estreia do Brasil na copa resolvendo mais problemas de maratona! Todos conhecem o jogo de dominós, em que peças com dois valores devem ser colocadas na mesa em sequência, de tal forma que os valores de peças imediatamente vizinhas sejam iguais. O objetivo do problema 1331. Dominó é justamente esse: determinar se é possível formar uma sequência com todas as peças de dominó fornecidas.

Modelagem

Antes de resolver esse problema, irei fazer uma breve revisão sobre grafos. Falarei apenas do necessário para solucionar esse problema. Se você não sabe o que são grafos, eu sugiro fortemente que você estude um pouco sobre isso já que eles são uma ferramenta muito poderosa na resolução de problemas.

Em teoria de grafos, diz-se que um grafo possui um caminho euleriano se existe um caminho que visita cada aresta apenas uma vez. Com caso especial, um circuito Euleriano é um caminho Euleriano que começa e termina no mesmo vértice. O conceito foi introduzido por Leonard Euler para a resolução do famoso problema das sete pontes de Königsberg.

Em um grafo euleriano G todos os vértices têm grau par.

Prova: Seja G um grafo euleriano. Logo, por definição, ele contém um circuito euleriano. Assim, por cada vértice desse circuito, existe uma aresta que chega nesse vértice e outra que sai desse vértice. Como toda aresta faz parte do caminho, isto é, nenhuma aresta fica fora do caminho, necessariamente o número de arestas que passam por cada vértice é par.

Se removermos uma aresta de um grafo euleriano, ele deixara de ser euleriano, mas ainda conterá um caminho euleriano (é só começar e terminar o caminho nos vértices correspondentes as arestas removidas). Isso significa que um grafo que contém um caminho euleriano pode ter dois vértices de grau ímpar.

Voltando aos dominós, ligar peças, montar caminhos, é um forte indicio de que nosso problema pode ser resolvido usando-se grafos. Seja o seguinte grafo: G, onde os vértices são os números 0..6 e as arestas são os dominós. Será possível montar uma sequência com todos os dominós se, e somente se, G contiver um caminho euleriano. Em outras palavras, uma sequência de dominós não é nada mais do que um caminho euleriano onde eu peguei as arestas do grafo (os dominós) e enfileirei.

Note que os dominós podem formar um grafo que não é conexo, mas que possui dois sub grafos conexos e eulerianos, assim é necessário testar isso (com uma busca em profundidade por exemplo) para garantir que os dominós formem uma sequência única.

Implementação

11011. Desafio cartográfico

Primeiramente, bem vindo ao Spoj Tricks! Aqui você poderá encontrar a solução comentada para a maioria dos problemas do spoj.

Nesse post vamos falar do problema 11011. Desafio cartográfico. De modo resumido o problema pede que dado um mapa de cidades ligadas por estradas, determine a distância entre o par de cidades mais distantes.

Modelagem da Solução

O problema pede basicamente o diâmetro do grafo onde as cidades representam os vértices e as estradas as arestas.

Achar o diâmetro de um grafo qualquer não é um problema tão simples. Entretando, observando as outras restrições dadas no enunciado podemos simplificar nosso problema:

(a) todas as estradas são de mão dupla;
(b) todas as estradas possuem 1km de comprimento;
(c) toda estrada conecta apenas duas cidades,
(d) dadas duas cidades quaisquer A e B, só existe uma única maneira de chegar em A partindo de B, e vice-versa.

Ou seja, nosso grafo sempre será uma árvore, e calcular o diâmetro de uma árvore é um problema bem mais simples.

Diâmetro de uma Árvore

O diâmetro de um grafo (que no nosso caso é uma árvore) é o maior caminho mínimo do grafo. A solução mais ingênua para esse problema seria calcular todas as distâncias entre todas as folhas do grafo e escolher a maior delas. Entretanto podemos fazer muito melhor que isso. Para tanto, observe que:

O vértice mais distante de um vértice u qualquer do grafo é uma das extremidades do diâmetro do grafo.


Para simplificar, e sem perda de generalidade, vamos supor que o diâmetro do grafo é único. Ou seja, existe exatamente um par de vértices {u, v}, tal que o comprimento do caminho mínimo entre u e v seja o maior do grafo. É fácil de ver que tanto u, quanto v são folhas do grafo.

Pegue qualquer nó w, vamos mostrar (por contradição) que o vértice mais distante dele é u ou v. Suponha que o vértice encontrado é diferente, digamos z. Vamos considerar dois casos.

Primeiro suponha que w esteja no caminho de u para v. Sem perda de generalidade, suponha que o caminho wu não têm sobreposição com o caminho wz. Temos:

dist(w, z) ≥ dist(w, v). Mas sabemos que dist(w, z)  ≥ dist(w, u).
dist(u, z) = dist(u, w) + dist(w, z) ≥ dist(u, w) + dist(w, v) = dist(u, v). Isto contradiz a suposição de que d(u, v) é o diâmetro original da árvore.

Suponha agora que w não esteja sobre o caminho de u para v. Temos que ou o caminho wz se sobrepõe com o caminho uv ou está separado.

Caso existe sobreposição:
Considere o vértice y mais próximo de W e sobre a sobreposição dos caminhos. Sem perda de Assim, dist(y, z)  ≥ dist(y, v).

Como dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) = dist(u, v). O que leva novamente a uma contradição já que por hipotese {u, v} é  o diâmetro original da árvore.

Se os caminhos não se sobrepõem, tem que haver dois vértices um no caminho uv e outro no caminho wz que são os mais próximos, sejam estes vértices x e y. Assim dist(u, z) = dist(u, y) + dist(y, z) ≥ dist(u, y) + dist(y, v) > dist(u, x) + dist(x, v) = dist(u, v). Daí a suposição de que {u, v} é o diâmetro é contrariada.

cqd.


Desse modo, o cálculo do diâmetro de uma árvore pode ser feito usando-se duas buscas em profundidade (ou em largura), uma delas (partindo de qualquer vértice) para achar o vértice mais distante, que será uma das extremidades (u ou v) do diâmetro. E a outra partindo-se do vértice encontrado (u ou v) para se calcular efetivamente o diâmetro do grafo.

Complexidade da solução

Tanto a busca em profundidade quanto em largura têm complexidade O(E), sendo E o número de arestas do grafo.

Implementação

O código abaixo implementa a solução apresentada acima.

Se você copiou e colou o código acima você foi recompensado com um grande segmentation falt. Embora correto, o código tem um problema difícil de perceber. Ele é passível de um estouro de pilha! A pilha de ativação não é infinita, na realidade ela é bem pequena, e nosso código pode no pior caso  fazer 10^6 chamadas a função dsf (lembre-se 2 ≤ N ≤ 10^6) causando assim um estouro de pilha que acaba por nos apresentar a exclarecedora mensagem de seg falt :(. O código abaixo resolve esse problema emulando uma pilha de ativação e removendo a recursão da função dsf.