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! Para terminar o ano de boas, nada melhor do que resolver um probleminha fácil! Não é? Por isso, hoje vamos contar rotulos de produtos, já que é isso que o problema 11631. Número de Envelopes pede. Mais especificamente, a partir de uma lista de rótulos, queremos calcular o número máximo de envelopes que podemos formar, sendo que cada envelope tem que ter um rótulo de cada produto distinto.
Solução
Obviamente o número máximo de envelopes que podemos ter é igual ao número de rótulos do produto que temos menos rótulos.
Olá meus amigos nerds! Hoje vamos brincar de fatoração, já que é isso que o problema 1850. Conte os Fatores pede. Mais especificamente, dado um número n, calcular o número de diferentes fatores primos que ele tem.
Solução
Esse é um problema fácil, bom para resolver depois da ressaca de Natal. Um algoritmo simples de fatoração é a solução.
Olá meus amigos nerds! Hoje vamos falar de olimpíadas, já que o problema 11675. Olimpíadas trata, justamente, disso. Nossa tarefa é, dada a informação dos países que receberam medalhas, gerar a classificação dos países na competição. Nesta tarefa, os países serão identificados por números inteiros. O melhor colocado deve ser o país que conseguiu o maior número de medalhas overall. Se houver empate entre dois países, o melhor classificado é o que tem o menor número de identificação.
Solução
Esse problema é quase uma cópia do 11646 Olimpíadas. Um problema simples de ordenação. Basta ordenar os países de acordo com a regra dada e pronto.
Implementação
Para tornar o problema mais interessante, implementei eu mesmo o quicksort. No outro post eu expliquei um pouco de como é a implementação dele.
Olá meus amigos nerds. O circo político do Brasil está pegando fogo hoje. Por isso vou falar rapidinho, já que há coisas mais interessantes que resolver problemas agora.
Hoje vamos resolver conflitos na agenda do doutor Pedro, já que é isso que o problema 8699. Dentista pede para fazer. Mais especificamente, dada a agenda de Pedro, com todos os horários de consulta, determinar qual é o maior número de consultas que ele consegue atender.
Solução
Uma forma ótima de escolher qual a primeira consulta a atender (de modo a maximizar o número total de consultas atendidas) é escolher aquela que acabaria primeiro. Pois, nesse caso, Pedro ficaria disponível o mais cedo possível para atender uma nova consulta. Aplicando essa ideia recursivamente chegamos a solução do problema.
Dito de um modo mais algorítmico:
Ordene as consultas por tempo de término. Enquanto a lista de consultas não estiver vazia Atenda a primeira consulta da lista. Remova da lista cada consulta que o tempo de início é menor que o tempo de término da consulta que Pedro está atendendo no momento (como ele esta ocupado, ele não pode atender essas consultas)
Olá meus amigos nerds. Hoje vamos resolver um probleminha de matemática, já que é isso que o problema 3742. Feynman pede para fazer. Mais especificamente, quantos quadrados diferentes existem em um quadriculado de N x N quadrados?
Solução
Para responder essa pergunta basta somar quantos quadrados de 1, 2, ..., N existem no quadriculado.
Para descrever um quadrado em um quadriculado é preciso apenas de um ponto: o ponto de início do quadrado, a partir desse ponto todos os outros quadradinhos do quadriculado que o quadrado ocupa ficam determinados.
Dito isso, como o quadriculado tem N x N existem N^2 quadrados de tamanho 1.
Posso começar um quadrado de tamanho 2 em qualquer uma das N linhas e N colunas com excessão da última linha e coluna. Assim existem (N-1)*(N-1) = (N-1)^2 quadrados de tamanho 2.
Já quadrados de tamanho 3 não podem começar nas duas últimas linhas e colunas. Assim teríamos (N-2)*(N-2)=(N-2)^2 quadradinhos de tamanho 3.
...
Por fim existe apenas 1 quadrado de tamanho N.
Em outras palavras:
1 -> N^2
2 -> (N-1)^2
3 -> (N-2)^2
...
N -> 1
Então a resposta é a soma dos quadrados dos números de 1 a N.
Olá meus amigos nerds. Hoje vamos brincar (literalmente) de comer bolinhas de chocolate. Já que é isso que o problema 11629. Competiçăo de chocolate nos pede para fazer. Mais especificamente, dado o jogo em que dois jogadores comem bolinhas de chocolate de modo alternado, com a restrição de que há n bolinhas e que um jogador pode comer no máximo m delas de cada vez. Determinar quem ganha o jogo, se o jogador que começou ou o que jogou em segundo lugar.
Solução
Para quem já conhece, esse jogo é uma variação d Nim. A ideia para resolver esse problema é simples:
a) Se m >= n o jogador que começa pode comer todas as bolinhas de chocolate e ganhar o jogo.
b) Se m < n, teríamos.
1 Se há 1, 2, ..., m bolinhas restantes, então quem joga ganha (ele pode comer todas as bolinhas)
2 Se há m+1 bolinhas então quem joga perde, pois ele não pode comer todas as bolinhas e qualquer número de bolinhas que ele comer resulta em uma configuração em que o outro jogador pode comer todas as bolinhas.
3 Se há m+1,..., 2m+1 bolinhas quem joga ganha, basta comer de modo a restar m+1 bolinhas (cenário em que quem joga, ou seja, seu adversário perde, dado o item 2).
Do esposto acima é possível concluir que se n == 0 mod m+1 quem joga perde. Então vamos a indução (vale para 1, suponha que vale para n, prove que vale para n+1): Suponha que essa relação valha para n. Para n+1 teríamos:
n+1 == 1 mod m+1 já que n == 0 mod m+1, ou seja, quem joga ganha pois ele pode comer uma bolinha e deixar que o outro jogador perca, uma vez que o segundo jogador estará na situação em que n == 0 mod m+1. Logo a relação vale para n+1, cqd.
Olá meus amigos nerds. Como não podemos fazer muito para tirar a lama la do rio Doce, hoje vamos, pelo menos, ajudar a plantar algumas árvores. Já que é isso que o problema 8781. Floresta nos pede para fazer. Mais especificamente, dado o número de árvores que se deseja plantar, queremos saber de quantas formas elas podem ser plantadas, respeitando-se as restrições do problema.
Solução
Esse é essencialmente um problema de matemática. Queremos plantar carvalhos formando um quadriculado (um retângulo cheio de carvalhos dentro). Sejam a e b os lados desse retângulo. Então:
# de carvalhos dentro do retângulo = a*b
Como no centro de cada quadradinho de carvalhos temos que plantar um encalipto. O número de encaliptos plantados será:
# de encaliptos plantados = (a-1)*(b-1)
Assim o número total de árvores plantadas será:
n = ab + (a-1)*(b-1) = 2ab -a -b + 1
resolvendo em relação a b temos:
2ab - b = n + a - 1 b = (n + a - 1)/(2a - 1)
Ou seja, todos os pares de números inteiros da forma [a, (n+a-1)/(2a-1)] satisfazem as condições do problema. Então é só contar quantos pares desses números existem.
Como retângulos axb e bxa não são considerados como elementos distintos, podemos supor que a <= b, assim:
a <= (n + a - 1)/(2a - 1)
donde tiramos a condição de parada do for: 2*a^2 - 2*a + 1 <= n
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.
Olá meus amigos nerds. Quando se mora sozinho, cozinhar passa a ser um problema, principalmente se você não gosta de jogar comida fora e não tem muito tempo livre (eu que o diga kkk). Uma solução para isso é comer besteiras, tipo miojo. Como somos muito bonzinhos, hoje vamos ajudar o pobre do João a preparar miojos. Já que é isso que o problema 3826. Miojo nos pede para fazer. Mais especificamente, dadas duas ampulhetas (os únicos 'relógios' que ele tem), capazes de medir tempos a e b diferentes e o tempo T necessário para se fazer o miojo, determinar qual será o tempo total gasto para preparar o miojo, incluindo o tempo gasto esperando as ampulhetas estarem em um estado capaz de medir o tempo exato do cozimento do miojo.
Solução
Podemos pensar nesse problema como um problema de decisão. Qual das ampulhetas deve ser virada em seguida para que sejamos capazes de medir exatamente T minutos? Como não podemos inferir a resposta para essa questão, temos que tentar todas as possibilidades e ver qual delas resulta em um menor tempo total.
Os únicos instantes que nos interessam seriam os momentos em que viramos uma ampulheta. Podemos começar virando a ampulheta a, a ampulheta b, ou ambas ao mesmo tempo. Quando uma ampulheta acaba de contar, temos duas opções: (1) vira-la e deixar que ela recomece a contar ou (2) virar as duas ampulhetas, assim a outra ira contar o tempo correspondente a parte da areia que já caiu em seu compartimento inferior. Fazendo-se um backtracking, baseado nessas condições somos capazes de calcular o tempo total.
A condição de parada é que uma das ampulhetas seja capaz de medir exatamente T minutos com a areia remanescente em sua parte superior.
Possivelmente esse problema possui uma solução mais elaborada usando-se teoria dos números (mmc, mdc, etc), mas como a solução por força bruta não é difícil de implementar, resolvi testa-la primeiro e ela se mostrou suficientemente boa para o problema receber um acept.
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.
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.
Olá meus amigos nerds. Hoje vamos verificar se dois códigos bancários pertencem a um mesmo banco ou não. Já que é isso que o problema 8709. Fusões nos pede para fazer. Mais especificamente, dados uma lista de bancos e uma série de fusões entre dois bancos, responder se dois bancos (identificados por seus códigos bancários) são o mesmo banco ou não.
Solução
Esse é um problema fácil. Já resolvemos alguns problemas bem parecidos aqui no blog. O único desafio aqui é fazer união de conjuntos de modo eficiente. Isso pode ser feito usando uma dijoint set forest que implementa tanto a operação de union quanto de find de forma eficiente (O(1)).
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.
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é!
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.
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.
Olá meus amigos nerds. Hoje vamos ver como fusos horários podem ser problemáticos. Já que é isso que o problema 20860. Voo nos pede para fazer. Mais especificamente, dados os horários de partida e chegada de um voo de ida e de um vôo volta entre duas cidades; determinar o tempo real de vôo bem como a diferença de fusos entre as cidades.
Solução
Quando li o problema achei que ele seria fácil, mas não é bem assim, ele impõe algum desafio. O segredo do problema está em perceber que: se em um trecho a diferença de fusos horários aumenta o tempo de viagem, no outro ela diminui o tempo. Assim se tirarmos a média entre os tempos totais de ida e volta teremos o tempo real de viajem, já que o fuso se cancela.
tempo_real = (tempo_ida + tempo_volta) / 2
Para encontrarmos o fuso bastaria subtrair o tempo real do tempo de ida ou de volta, isto é:
fuso = tempo_ida - tempo_real
Mas isso não resolve completamente o problema, já que, como o próprio problema afirma, as datas não estão completas. Ou seja, não sabemos se a data de chegada é a mesma da de saída ou se refere ao próximo dia. Assim para uma mesma entrada teríamos várias respostas, para desambiguar essas respostas o problema nos garante que a viajem durou menos de 12 horas.
Mas como poderíamos usar esse dado? Se pensarmos bem os tempos de viajem considerando que o avião chegou no mesmo dia e no dia seguinte diferem de no máximo 12 horas. Assim se tomarmos o módulo teremos o tempo pedido. Assim:
tempo_real = (tempo_ida + tempo_volta) / 2 mod 12
Lembrando que o fuso tem que ficar no intervalo -12 < fuso < 12 teríamos:
fuso = tempo_ida - tempo_real mod 24 if fuso > 12 fuso -= 24
Olá meus amigos nerds. Hoje vamos brincar de abrir fechaduras. Já que é isso que o problema 19949. Fechadura nos pede para fazer. Mais especificamente, dados uma serie de números (que representam a altura dos pinos da fechadura) e uma posição em que os pinos tem que ser colocados para que a fechadura se abra, determinar qual o número mínimo de movimentos de elevar ou abaixar os pinos para que a fechadura se abra.
Solução
Quando li esse problema pela primeira vez, achei que sua solução envolveria programação dinâmica, já que ele pedia o menor número de movimentos. Entretanto se observarmos bem, o problema afirma que quando um pino é mexido o da frente também o é. Assim, não há o que otimizar, basta percorrer o vetor com as alturas (armazenando o número de movimentos gastos para mover o pino anterior) e ir somando o número de movimentos necessários.
Seja 'altura' o vetor com as alturas dos pinos Seja m a altura que devemos colocar os pinos soma_mov = 0 acum = 0 for altura in alturas diff = m - (altura + acum) soma_mov += abs(diff) acum = diff
Olá meus amigos nerds. Hoje vamos fazer um algoritmo para detectar se dois retângulos se interceptam ou não. Já que é isso que o problema 19958. Detectando Colisões nos pede para fazer. Mais especificamente, dados dois retângulos, que tem seus lados paralelos aos eixos, determinar se há alguma interseção entre eles.
Solução
O caso geral desse problema, que é determinar se dois polígonos tem pontos de interseção é bem complexo. Para nos ajudar, o problema trata apenas de retângulos e ainda fixa que seus lados são paralelos aos eixos. Ai fica fácil né!
O problema nos fornece os cantos inferior esquerdo e superior direito de cada retângulo. Vamos tentar estabelecer as condições para que os dois retângulos não possam se interceptar.
Caso o canto superior direito de um dos retângulos esteja 'atráz' do canto inferior esquerdo do outro não há como haver interseção pois nesse caso um retângulo 'termina' antes que o outro comece. Da mesma forma, se o canto superior direito de um dos retângulos estiver 'abaixo' do canto inferior esquerdo do outro um dos retângulos terá 'terminado' antes do outro começar. Pensando nas coordenadas x,y desses pontos teríamos (sendo a e b os retângulos):
if (a_sup_dir_x < b_inf_esq_x || a_sup_dir_y < b_inf_esq_y || b_sup_dir_x < a_inf_esq_x || b_sup_dir_y < a_inf_esq_y ) responda não
A condição acima é necessária. Agora vou mostrar que ela é suficiente. Observe que na situação dos dois cantos superiores da direita estarem no sub espaço acima e a direita dos cantos inferiores, os seguimentos (a_inf_esq, a_sup_dir) e (b_inf_esq, b_sup_dir) seriam tanto diagonais do retângulo formado pelos pontos (a_inf_esq, b_sup_dir, a_sup_dir, b_inf_esq) quanto dos retângulos originais, mas como as diagonais de um retângulo sempre se interseptam, resulta que esse ponto pertencerá a uma diagonal de cada um dos retângulos a e b e assim eles também se interceptam.
Olá meus amigos nerds. Esse mês demorei um pouco a dar as caras por aqui, mas foi por uma boa causa, estava escrevendo um paper :P algo que eu não fazia há muito tempo. E não seria um paper se eu não tivesse que ficar escrevendo e reescrevendo tudo até de madrugada. Vocês não acham? kkk.
Hoje ajudar vamos ajudar nossos amigos da obi a vender algumas casas. Já que é isso que o problema 18543. Vende-se nos pede para fazer. Mais especificamente, (por culpa da Dilma) a obi precisa vender alguns de seus imóveis e quer que os que restarem estejam o mais próximos possível, ou seja, que a distância entre o primeiro e o último prédios restantes deve ser a menor possível.
Solução
Devo dizer que esse é um problema fácil e quase não tive vontade de escrever sobre ele. Mas esse foi o único problema que eu resolvi essa semana. Então vai ter que servir.
Devemos perceber que as casas restantes serão necessariamente consecutivas (pensando na distância para o início da rua). É só você pensar que para vender uma casa no 'meio' das que restaram, uma casa fora da sequência não poderia ser vendida, mas a distância dessa casa para a casa do canto oposto das que sobraram aumentaria.
Assim basta ordenar as casas pela distância. E percorrer a lista de casas computando a distância pedida.
Implementação
Me desculpem pelo código feio, mas é que eu o fiz enquanto assistia uma palestra chata sobre devops :P
Olá meus amigos nerds. Hoje vamos ajudar nosso amigo fotografo a descobrir quantas fotos ele precisa tirar para ter uma foto nítida de todos os objetos de sua cena. Já que é isso que o problema 11609. Foco nos pede para fazer. Mais especificamente, dados os intervalos contendo objetos que o fotografo quer fotografar, determinar qual é o mínimo de fotos que ele tem que tirar para que haja pelo menos uma foto de cada intervalo.
Solução
Esse problema é muito similar ao da semana passada (18553 - Janela). Vou usar o mesmo raciocínio que usei lá aqui.
O problema consiste em encontrar as interseções dos intervalos, pois assim eu posso tirar uma foto apenas da interseção dos intervalos e assim economizar fotos.
Pense nos intervalos ordenados pelo ponto em que eles terminam. Eu preciso de pelo menos uma foto do primeiro intervalo, sendo assim vou escolher tira-la no ponto onde este intervalo acaba. Dessa forma eu posso aproveitar essa foto para todos os intervalos subsequentes em que o ponto de inicio desses intervalos seja menor que o ponto que eu tirei a foto. Esse algoritmo é ótimo, pois eu necessariamente tenho que tirar uma foto do primeiro intervalo. Basta agora eu remover todos os intervalos que eu já tirei uma foto e repetir o passo anterior até que não sobre nenhum intervalo. De forma mais algorítmica teríamos:
Seja S o conjunto dos intervalos ordenados pela coordenada do seu ponto de fim num_fotos = 0 pos_atual = 0 para cada intervalo X in S if X.inicio > pos_atual num_fotos++ pos_atual = X.fim
Observe que pos_atual marca até que ponto da reta nós já avaliamos (pensando nos intervalos sobre uma reta), ou seja, qual é o ponto em que o intervalo anterior termina. O if evita que incrementemos num_fotos caso o inicio do intervalo se sobreponha ao intervalo anterior, o que na prática é o mesmo que remover o intervalo atual da lista.
Olá meus amigos nerds. Hoje vamos calcular a área aberta de uma janela. Já que é isso que o problema 18553. Janela nos pede para fazer. Mais especificamente, dadas as posições de vários pedaços de vidro e seus comprimentos e o comprimento total da janela determinar qual a área total da janela que está aberta.
Solução
Devo confessar, quando comecei a ler esse problema pensei que ele seria um pouco mais difícil, mas o tamanho da entrada (3) é tão pequeno que por força bruta é possível faze-lo. Vou ignorar esse fato e mostrar como seria possível resolver esse problema, caso os vidros da janela fossem de tamanhos diferentes e em maior número.
O problema consiste em encontrar pedaços da janela que não estejam cobertos por nenhum vidro. Qual é a condição necessária e suficiente para que um pedaço da janela não esteja coberto? Se pensarmos bem, essa condição é até bem simples (depois que a vemos, é claro!). Um buraco é definido por um fim de janela e pelo inicio da primeira janela seguinte, ou seja, só pode haver um buraco se o ponto de inicio de uma janela for maior que o ponto de termino da janela anterior.
Mas como garantir que não existiram outros pedaços de vidro entre esses pontos? Isso é fácil, basta ordenar os pedaços de janela pelo ponto em que elas terminam. Pense nos pedaços i e i+1 ordenados. Não pode haver uma janela que termine em um ponto entre o fim de i e de i+1, caso contrário i e i+1 não poderiam seguir um ao outro na ordenação, deveriam ter o ponto de fim desse terceiro pedaço entre eles.
Sendo assim, a solução do problema consiste em ordenar os pedaços de vidro pelo seu ponto de fim e ir somando os espaços entre o inicio da próxima janela e o fim da anterior.
Olá meus amigos nerds. Hoje vamos tentar descobrir qual é o maior número que podemos formar apagando D dígitos de um número de N dígitos. Já que é isso que o problema 3237. Apagando e ganhando nos pede para fazer.
Eu tenho uma história engraçada com esse problema. Em uma regional da maratona de programação do ICPC eu consegui resolver-lo, mas meu colega de time me convenceu que minha solução estava errada (mesmo estando certa). No final, faltou justamente esse problema para passarmos de fase. Quem mandou eu ser burro kkk.
Solução
Existe uma solução trivial para esse problema:
Seja num o número de N digitos dado max = 0 while d > 0 d-- m = 0 for i in len(num) Seja x o número obtido apagando o i-ésimo digito de num m = maximo(x, m) max = maximo (m, max)
Obviamente ela não passa no tempo! Isso porque a comparação entre x e m tem complexidade N (o número de bits de x), sendo a complexidade do algoritmo O(d*N^2), o que é muito ineficiente para o problema.
Pense comigo, dados dois números com a mesma quantidade de dígitos, qual deles é maior? Aquele que tem o digito mais a esquerda maior, oras. Essa simples observação nos fornece um algoritmo guloso capaz de responder o problema. Se o primeiro dígito da esquerda for menor que o segundo, a decisão de apagar o primeiro dígito é ótima. Assim:
Seja num uma lista com os N digitos dados i = num.begin() j = i++ while i != num.end() if == 0 pare if num[i] < num[j] apaga(num[i]) else i++
Se conseguirmos apagar os d dígitos usando a observação do parágrafo anterior o problema está resolvido. Pode ocorrer que não consigamos fazer isso, nesse caso, os dígitos do início do número estaram em ordem estritamente decrescente. Basta então repetir o processo acima do fim para o inicio do número para apagar os dígitos que faltam.
Observe que o algoritmo acima é muito mais rápido, tendo complexidade O(N).
Implementação
Observe que em c++ list.erase(it) apaga e invalida o iterador o que nos força a função apaga para evitar problemas.
Olá meus amigos nerds. Hoje completa exatamente um ano que eu resolvi um problema relacionado a moedas. E para comemorar, nada melhor do que resolver outro problema do tipo. Vamos tentar verificar se é possível pagar uma conta de modo exato apenas com as moedas que estão em nosso bolso. Já que é isso que o problema 18550. Troco nos pede para fazer. Mais especificamente, dadas m moedas, determinar se é possível somar exatamente v centavos usando um subconjunto dessas moedas.
Solução
Como todo problema de programação dinâmica esse não é fácil. Uma solução que enumere todos os conjutos possíveis de moedas e verifique se eles somam v não viável.
O segredo, para resolver esse problema, esta em pensar o que acontece quando eu pego uma moeda. Suponha que eu conheça todos os valores que eu consigo somar com as moedas restantes, se a cada um desses valores, eu somar a moeda atual eu fico com um novo conjunto de valores que eu consigo somar. A união desse conjunto e do anterior forma todas as somas que eu consigo fazer até o momento.
Isso sugere uma solução usando programação dinâmica. Com 0 moedas eu só consigo somar 0. Adicionando a primeira moeda eu só consigo somar 0 e o valor da moeda. Com a segunda eu já consigo somar 0, o valor da primeira, o valor da segunda e a soma das duas... Ou seja, se eu armazenar para cada valor possível de soma (menor ou igual a v é claro) se é possível somar aquele valor, para adicionar uma moeda é só eu percorrer esse vetor de estados e ir atualizando as posições dele com as novas somas possíveis.
A ideia acima funciona pois: se já é possível somar x com um conjunto de moedas, se eu adicionar mais uma moeda ao problema, continua sendo possível eu somar x (basta eu não usar a nova moeda). Se eu consigo somar a, b e c e eu adiciono outra moeda (d) ao problema eu vou poder somar além de a, b e c, (a+d), (b+d), (c+d). Algoritmicamente falando:
somas_possiveis = {0} para cada moeda x para cada soma em somas_possiveis novas_somas += (x+soma) somas_possiveis |= novas_somas
Ou considerando que somas_possiveis sera representado por um vetor somas_possiveis[0] = True para cada moeda x para i=len(somas_possiveis), i >= x, i-- Se somas_possiveis[i-x] somas_possiveis[i] = True
Note que se eu posso somar i-x centavos, se eu adicionar a moeda atual eu posso somar i centavos. O loop é feito de forma decrescente para garantir que eu não use x duas vezes para uma mesma soma, já que i-x ainda não foi calculado para a moeda atual.
Note que a solução apresentada depende do valor de v, ou seja, é uma solução pseudo polinomial. Mais precisamente a complexidade dessa solução é O(v*m), como v e m são relativamente pequenos essa solução é suficiente para conseguirmos superar o time limit.
Implementação
:P O operador -- serve para alguma coisa! Observe que se invertermos a lógica do loop da linha 22 para uma lógica aditiva o programa deixa de produzir a resposta certa, pois nesse caso quebramos nosso invariante de que somas_possiveis[v-moeda] não utiliza a moeda atual para ser somado.
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.
Olá meus amigos nerds. Hoje vamos brincar de Pacman, já que é isso que o problema 19948. PacMan nos pede para fazer. Mais especificamente, dadas as posições do pacman, comida e fantasmas determinar quantos pontos o pacman consegue fazer.
Solução
Vou confessar que não resisti a tentação de escrever sobre um problema com esse nome, mesmo que ele seja muito fácil (o que obviamente eu só descobri após o ler :P). Basta iterar sobre a matriz que representa o campo de jogo e contar quantos pontos o jogador faria usando a estratégia descrita no problema. É só zerar os pontos se ele encontrar um fantasma, e imprimir no final a maior quantidade de pontos que ele fez.
