Esse blog se destina a todos os nerds que não têm tempo para uma boa vida social, pois são atormentados por não conseguirem resolver os problemas do spoj. Aqui você poderá encontrar soluções comentadas para uma grande variedade de problemas relacionados a competições de programação.
Olá meus amigos nerds. Hoje vamos estudar um pouco sobre máximos e mínimos em um gráfico. Já que é isso que o problema 3242. Loop musical nos pede para fazer. Mais especificamente, dado um conjunto de pontos formando um gráfico, determinar quantos mínimos e máximos locais esse gráfico possúi.
Solução
Para quem se lembra das aulas de cálculo, esse é um problema fácil. Mínimos e máximos locais são pontos de inflexão do gráfico, isto é pontos em que a derivada é nula. Isso significa que, dados três pontos, existe pelo menos um mínimo (ou máximo) local entre esses pontos se o sinal da derivada se alterar entre eles. Para que isso ocorra, basta que o ponto do meio seja mais alto, ou mais baixo, que os outros dois pontos.
Então basta testar se isso ocorre e lembrar que no problema os pontos formam um loop, ou seja, o primeiro ponto segue o último ponto.
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.
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 :)
Olá meus amigos nerds. Hoje vamos brincar de arquitetos e ajudar o senhor Bloggs a planejar uma cidade. Já que é isso que o problema 18536. Capital nos pede para fazer. Mais especificamente, nossa tarefa é determinar, se dados quatro valores de área (a1, a2, a3 e a4) determinar se é possível formar um retângulo que tenha area igual a soma das quatro áreas.
Solução
Problemas de geometria costumam ser bastante complexos, mas esse não é muito difícil. Para começar sabemos de duas coisas: o valor de cada uma das quatro áreas e que elas são necessariamente retangulares. Entretanto não conhecemos os lados de cada retângulo (é isso que queremos determinar).
Note que juntar, quatro áreas (retangulares) e formar um retângulo é equivalente a dado um retângulo dividí-lo em quatro outros retângulos. Vamos, então resolver esse problema. Observe a figura abaixo:
Onde temos um retângulo de lados a e b. Observe que:
a = x1 + x2 b = y1 + y2
Sejam A1, A2, A3 e A4 as quatro áreas dadas. Da figura, podemos escrever as áreas como:
x1*y1 = A1 x2*y1 = A2 x1*y2 = A3 x2*y2 = A4
Note que temos quatro variáveis e quatro equações, mas infelizmente esse não é um sistema linear. Mesmo assim podemos isolar y1 nas duas primeiras equações (supondo x1 e x2 diferentes de 0):
O que implica: A3/x1 = A4/x2 => A3*x2 = A4*x1 => A3*x2 - A4*x1 = 0
O que resulta no seguinte sistema homogêneo: A1*x2 - A2*x1 = 0 A3*x2 - A4*x1 = 0
Se o sistema possuir solução única ela será trivial (x1=x2=0). Essa solução não nos serve! Já que supusemos que x1, x2, x3 e x4 eram diferentes de 0 no inicio de nossa dedução. Ou melhor, essa solução indica que não é possível construir o retângulo com as quatro áreas dadas.
Nos resta ainda a possibilidade de esse sistema ter infinitas soluções (lembre-se, um sistema homogêneo nunca é impossível). Nesse caso podemos escolher algum x1, x2, diferentes de 0 (e maiores que 0, já que se tratam de lados de um retângulo). Para isso, o determinante da equação deve ser nulo, ou seja:
A1*A4 == A2*A3
Eu queria dizer que já está resolvido, mas falta ainda uma parte importante. Em nossa discussão supusemos que conhecíamos A1, A2, A3 e A4, mas na realidade não conhecemos a ordem em que as áreas devem ser testadas na equação acima, sendo assim temos que testar todas as permutações para ter certeza que alguma satisfaz a equação.
Implementação
Quem vê esse código até pensa que o problema é muito fácil! Ledo engano...
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.
