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.

18552. Famílias de Troia

Olá meus amigos nerds. Hoje vamos brincar com árvores genealógicas para tentar descobrir quantas famílias sobreviveram a guerra de Tróia. Já que é isso que o problema 18552. Famílias de Troia nos pede para fazer. Mais especificamente, dadas as relações de parentesco entre os sobreviventes da guerra de Tróia, determinar quantas famílias sobreviveram.

Solução

Aqui vale um disclaimer, quando eu resolvi esse problema a descrição da entrada estava errada. A primeira linha contem dois inteiros n (número de sobreviventes e m (total de relações entre famílias). Siga o formato dos exemplos que ele está certo.

Uma abordagem modelando o problema com grafos e aplicando uma busca em profundidade (ou largura) resolveria esse problema. Mas eu quero dar uma solução um pouco mais eficiente e simples.

Pense nas famílias como conjuntos, comece com cada sobrevivente como pertencente a um conjunto (formado apenas por ele), quando descobrimos que dois sobreviventes pertencem a uma mesma família faça a união dos conjuntos que esses sobreviventes pertencem. A solução para o problema será o número de conjutos existente ao final. Simples não!? O problema agora é só de como representar os conjuntos de forma que operações de união e pertinência sejam executadas de modo eficiente. Mas isso é justamente o que um dijoint forest set faz, então o problema se torna trivial.

Implementação

Note o uso que fiz dos argumentos de um template para parametrizar o tamanho máximo dos vetores que compõe a classe dsf.

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