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 brincar fazer trilhas, já que é isso que o problema 2609. Trilhas nos pede para fazer. Mais especificamente, dadas as informações sobre distâncias e altitudes de um conjunto de trilhas, determinar qual é a trilha que exige o menor esforço de subida. Onde o esforço de subida é proporcional ao desnível do trecho percorrido.
Solução
O problema não nos diz como calcular o esforço de subida, mas apenas que ele é proporcional ao desnível do trecho, em outras palavras à altura do trecho subido. Ora mas se o esforço é proporcional a cada uma das alturas ele será proporcional a soma delas. Sendo assim, o problema fica bem fácil, basta calcular a soma das alturas. Para isso, é só percorrer o vetor com a altura dos trechos e ir fazendo as diferenças entre dois trechos seguidos.
Um detalhe importante é que ele não se importa com o sentido do trecho, assim sendo devemos calcular o desnível do terreno considerando que ele pode estar indo do trecho a para o b, ou vice versa.
A resposta final será a opção de trilha com a menor soma das alturas.
Olá meus amigos nerds. Dizem que livrinhos de colorir estão na moda hoje em dia. Se isso é verdade eu não sei, mas sei que hoje vamos brincar de colorir alguns, já que é isso que o problema 11006. Colorindo nos pede para fazer. Mais especificamente, dados um desenho quadriculado e um ponto que se deseja começar a colorir, devemos determinar quantos quadrados desse desenho serão coloridos no total sendo que se eu colorir um quadrado devo colorir todos os seus vizinhos a menos que eles já estejam coloridos.
Solução
Esse é um problema bem simples. O processo de colorir descrito no problema é exatamente uma busca em largura, feita sobre o papel quadriculado. Sendo assim basta executarmos a busca e contarmos quantos quadradinhos serão coloridos ao final do processo.
Implementação
Lembram que no problema anterior eu preenchi as bordas da matriz com 0's. Vejam que nesse problema, como eu não fiz isso a cada iteração do loop eu tenho que ficar checando se x e y estão de fato dentro da matriz.
Olá meus amigos nerds. Hoje vamos determinar onde um robô de limpeza deve parar depois de limpar um salão. Meio chato, mas nem só de coisas legais vive o mundo, né! Já que é isso que o problema 18538. Robô nos pede para fazer. Mais especificamente, dados um mapa indicando a cor de cada ladrilho no chão e a posição inicial do robô, devemos determinar a posição final do robô que só se locomove através de ladrilhos pretos.
Solução
Esse é um problema bem simples. Basta simularmos a trajetória do robô. Para isso, basta ir iterando sobre a posição atual do robô procurando pela próxima posição válida. Para não correr o risco de voltar pelo mesmo caminho que o robô veio, basta ir apagando o caminho a medida que ele vai sendo percorrido.
Implementação
Observe como envolvo a minha matriz com 0's (sentinelas) para evitar que a busca saia dos limites da matriz e eu tenha que ficar verificando isso no código.
Olá meus amigos nerds. Hoje vamos brincar de cortar pães para fazermos sanduíches que serão usados durante uma maratona de programação. Isso mesmo! Já que é isso que o problema 12939. Pão a metro nos pede para fazer. Mais especificamente, dados os tamanhos de pão disponíveis (em centímetros) e a quantidade de pessoas a serem servidas, queremos saber o tamanho inteiro máximo (em centímetros) da fatia que pode ser cortada de maneira a atender todas as pessoas.
Solução
A solução simples para esse problema seria tentar todos os tamanhos possíveis para os pães e escolher o maior. Entretanto, isso, é claro, não é eficiente o suficiente.
Suponha que conheçamos o tamanho de pão máximo. Para tamanhos superiores de pão não conseguimos servir as n pessoas (caso contrário por contradição esse tamanho não seria máximo). Assim, ao invés de procurar por força bruta o tamanho ótimo, podemos aplicar busca binária ao problema, uma vez que temos uma propriedade que é verificada para valores inferiores a um número (o tamanho máximo), mas não o é para valores inferiores.
Agora só nos falta definir os limites nos quais queremos aplicar busca binária. Obviamente, o tamanho mínimo de pão é 1. Já o máximo é o maior tamanho entre as k fatias de pão (lembre-se de que não podemos juntar duas fatias).
Implementação
Observe que o código testa duas condições de contorno. Uma delas é o pão de tamanho 1 (limite inferior do intervalo) e outra o pão de tamanho k (todos os pedaços são do mesmo tamanho).
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.
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:
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.
Olá meus amigos nerds, depois de um bom hiato, devido a eu ter me mudado e ficado algum tempo sem internet :(, estamos de volta para resolver mais problemas.
Mas para compensar hoje vamos resolver um tipo de problema que eu gosto muito: um problema que a solução fácil, não é suficientemente boa, nos forçando a ir além e fazer melhor.
Hoje vamos verificar qual a cor que mais aparece durante um desfile de patos. Já que é isso que o problema 17384. Desfile dos Patos nos pede. Mais especificamente, dada uma fila de patos, em que cada pato tem uma plumagem de cor diferente, determinar qual é a cor majoritária dentre as cores da plumagem dos patos, isto é, a cor que aparece em mais da metade das plumagens.
Solução
Apesar da aparente simplicidade esse problema é bem difícil. Ele possuí um limite de tempo muito apertado, e isso faz com que algo que geralmente não é muito importante, quando tratamos de complexidade de algoritmos, se tornar relevante, as constantes.
Vocês já devem ter percebido que um simples mapa resolve o problema, isto é armazene contadores para cada cor e no final verifique qual cor majoritária. Se implementarmos o mapa como um hash, esse algoritmo é linear. Além disso, ele tem complexidade ótima, já que não é possível resolver esse problema sem analisar cada elemento da lista.
Entretanto o algoritmo acima não é eficiente o suficiente para resolvermos esse problema. Quem diria, um hash não é eficiente o suficiente para resolve-lo! Depois de muito pensar (e até achar que quem inseriu o problema cometeu algum equivoco no time limit), observamos que o problema tem uma característica especial, a cor mais frequente é majoritária, isso é ela tem mais aparições na lista que a soma de todas as outras cores. Isso nos permite abrir mão do hash e usar um único contador para verificar qual é a cor majoritária.
A ideia é a seguinte, se do número de aparições da cor majoritária subtrairmos o número de aparições de cada uma das outras cores, esse resultado é necessariamente maior que 0. Assim, podemos usar um algoritmo guloso para contar a diferença entre o número de aparições da cor majoritária para as outras cores. Podemos iniciar nossa contagem com qualquer cor, já que ao final necessariamente a cor majoritária tem elementos o suficiente para "cancelar" com cada um dos elementos das outras cores. O algoritmo abaixo vai verificando qual a cor majoritária até a 0-ésima posição do vetor, 1-ésima posição, ..., n-ésima, etc
corMajoritaria = 0 cnt = 0 for cor in corPatos if cnt == 0 corMajoritaria = cor if cor == corMajoritaria cnt++ else cnt--
O algorítmo acima é mais eficiente que um hash, pois não tem que pagar o custo de iterar sobre todos os elementos do hash ao final para verificar qual é o que tem o maior contador.
