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

18542. Tiro ao Alvo

Olá meus amigos nerds. Hoje vamos brincar de tiro ao alvo. Já que é isso que o problema 18542. Tiro ao Alvo nos pede para fazer. Mais especificamente, dadas as posições onde acertamos o alvo, e o tamanho de cada círculo do alvo, determinar quantos pontos nós fizemos. O número de pontos que um tiro alcança é igual ao número de círculos que ele ficou dentro.

Solução

O segredo desse problema é como contar o número de círculos que um tiro está dentro de forma eficiente. E isso não é muito difícil de fazer se lembrarmos que um ponto é interior a circunfência se:

x^2 + y^2 <= r^2

onde x e y são as coordenadas do ponto e r é o raio do círculo.

Testar essa relação para cada ponto e cada raio é ineficiente (O(C*T)). Entretanto, note que, se um ponto é interior a um círculo ele o será a todos os círculos com raios maiores. Então se ordenarmos os círculos pelos seus raios podemos utilizar busca binária para achar a posição em que o ponto deveria estar no array e dessa forma achar quantos círculos tem raio maior que o ponto. Assim:

pontos_ganhos(x,y) = C - posição de (x,y) no array de raios

onde C é o número de círculos.

Implementação

Note que o número de pontos pode não caber em uma variável do tipo int. Temos que usar um long long int (que tem pelo menos 64bits) para conseguir resolver o problema.

Observe, também, o uso da função lower_bound, que indica a posição do array que o valor passado como parâmetro deveria ocupar. lower_bound internamente implementa uma busca binária.

Por fim observe que a diferença entre dois ponteiros (pos - raios) resulta no número de elementos entre eles e não um endereço de memória.

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.