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, ainda não é hoje que vou apresentar a vocês meu recomendador de problemas (quero melhorar o algoritmo de recomendação um pouco mais primeiro). Mesmo assim, hoje vou resolver um outro problema que foi recomendado por ele.
Hoje vamos brincar de bingo, já que é isso que o problema 9002. Bingo! nos pede. Albert, Charles e Mary (ACM rsrs) resolveram criar um novo tipo de bingo, nesse jogo são sorteadas, com reposição, duas bolas e o número sorteado é a diferença absoluta desses números. Como ACM não são bons de matemática eles nos pediram para verificar se dado um conjunto de bolas é possível se sortear todos os números.
Solução
Ao ler esse problema pensei que ele poderia ser interessante, mas ao olhar os limites da entrada fiquei decepicionado (n <= 90), ou seja, qualquer algoritmo de força bruta seria bom o suficiente.
Resolver esse problema usando força bruta é trivial. O seguinte algoritmo (com complexidade O(n^2)) faz isso:
para cada par (x, y) de bolas compute a diferença entre x e y armazene essa diferença verifique se os números de 0 a N estão no conjunto das diferenças armazenadas
Implementação
Essa dica é meio trivial, mas vai lá assim mesmo: Observe como eu usei o vetor possiveisDiffs para armazenar todas as diferenças de modo mais eficiente.
Olá meus amigos nerds, tenho boas notícias para hoje. Vocês se lembram que eu comentei aqui que eu estava implementando um recomendador de problemas, para facilitar a vida de quem usa o spoj. Pois é, essa semana consegui dar mais um pequeno passo e implementar alguns algoritmos mais simples para fazer isso. E nada melhor do que testar um algoritmo implementando outro, não é verdade? Assim o problema que vamos resolver hoje nos foi sugerido por um dos algoritmos de recomendação que implementei. Não vou falar do recomendador hoje, pois pretendo dissecar esse assunto mais a fundo nas próximas semanas.
O problema de hoje é o 3597. Par ou Ímpar e ele nos pede que ajudemos Joaõzinho e Maria a resolverem a confusão que eles fizeram em uma brincadeira de par ou ímpar. Eles jogaram muitas vezes par ou ímpar e anotaram os resultados em cartões. Em todos os jogos João escolheu ímpar (e, conseqüentemente, Maria escolheu par). Durante os jogos cada jogador escreveu nos cartões quantos dedos ele/ela mostrou, usando uma carta para cada jogo. O objetivo deles era ser capar de re-checar os resultados depois, procurando pelos cartões de cada jogo. Entretanto, no fim do jogo os cartões de cada jogador estavam fora de ordem o que impedia que eles contassem exatamente quantas partidas cada um ganhou.
Mais especificamente, o problema nos pede que dado o conjunto de números escritos nos cartões, determinar o número mínimo de jogos que Maria certamente ganhou.
Solução
Observe que é impossível saber quantos jogos cada um ganhou exatamente. Entretanto, independente de quantos jogos cada um ganhou o seguinte invariante deve se manter:
jogos_ganhos_maria + jogos_ganhos_joao = n
onde n é o total de jogos disputados.
Como é muito difícil calcular diretamente o número mínimo de jogos que Maria ganhou, vou resolver o problema reverso: calcular qual é o máximo de jogos que João pode ganhar. Esse tipo de abordagem as vezes é bem útil, sendo aplicada em vários problemas de otmização.
Na situação que Maria ganha o mínimo de jogos possíveis, João necessariamente deve ganhar o maior número de jogos possíveis, assim:
min_jogos_ganhos_maria + max_jogos_ganhos_joao = n
ou
min_jogos_ganhos_maria = n - max_jogos_ganhos_joao
Só um lembrete:
par + par = par
par + ímpar = impar
ímpar + par = impar
ímpar + ímpar = par
Maximizar o número de jogos ganhos é fácil. Lendo o lembrete acima, você provavelmente já matou ou problema. Basta pensar que cada vez que João colocou um número par, Maria colocou um ímpar, e vice versa. Assim:
max_casamentos(joao_par, maria_impar) é fácil de calcular, e é igual ao mínimo entre joao_par e maria_impar. Assim:
max_jogos_ganhos_joao = min(joao_par, maria_impar) + min(joao_impar, maria_par)
logo min_jogos_ganhos_maria = n - min(joao_par, maria_impar) - min(joao_impar, maria_par)
E essa é justamente a solução do problema.
Olá meus amigos nerds, hoje estou com preguiça então falarei de um problema fácil. Mentirinha, estou é fazendo um recomendador de problemas para o spoj, em breve falarei mais sobre ele.
Por incrível que pareça existem dezenas de problemas fáceis no spoj. E o problema 1745. Recuperação é um deles. Nesse problema, é pedido que dado uma lista de inteiros se encontre um inteiro nessa lista tal que ele seja igual a soma dos outros inteiros que o antecedem na lista.
Solução
De forma mais formal queremos um número a[k] tal que:
a[k] = a[1] + a[2] + ... + a[k-1]
Então basta percorrer a lista e testar essa propriedade. É o que o algoritmo abaixo faz:
soma = 0 for cada elemento a[i] da lista if a[i] == soma numeroPedido = a[i] break; soma += a[i]
Basta então imprimir numeroPedido
Implementação
Observe que numeroPedido deve ser inicializado com um valor inválido (menor que a menor soma possível, ou maior que a maior soma possível), se você usar numeroPedido = -1 (eu fiz isso da primeira vez :P) você vai levar merecidamente um belo de um wrong answer.
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.
Olá meus amigos nerds, hoje falaremos um pouco de um dos problemas mais clássicos de programação dinâmica, o problema da mochila. E isso, graças ao nosso amigo Cuca, que saiu para jogar futebol e se esqueceu de se encontrar com sua namorada.
Mais especificamente, o problema 1389. Pedido de Desculpas nos pede que ajudemos Cuca a escrever um pedido de desculpas com o maior número de repetições da palavra desculpa. Para isso Cuca nos forneceu um conjunto pré escolhido de frases e quer usar essas frases para preencher um cartão de desculpas que cabe apenas um número limitado de caracteres.
Solução
O problema aqui é bastante simples, apenas se você já estudou um pouco de algoritmos (e consequentemente, conhece o problema da mochila booleana). Observe que podemos mapeá-lo da seguinte forma:
cartão = mochila tamanho das frases = peso dos objetos # de desculpas por frase = valor ($) dos objetos
Mochila Booleana
O problema da mochila é um problema de optimização combinatória. O nome dá-se devido ao modelo de uma situação em que é necessário preencher uma mochila com objetos de diferentes pesos e valores. O objetivo é que se preencha a mochila com o maior valor possível, não ultrapassando o peso máximo.
O problema da mochila é um dos 21 problemas NP-completos de Richard Karp. Isso quer dizer que sua solução tem complexidade O(2^n). Observe que, esse problema pode ser resolvido como um problema de decisão, ou seja, para cada objeto, decida se ele deve ou não ser colocado na mochila. Uma forma simples de se decidir pela adição ou não de um objeto é gerando todos os subconjuntos de objetos e escolhendo o subconjunto de maior valor:
melhorSolucao=0 foreach subconjunto dos objetos valor = calcule o valor desse subconjunto if valor > melhorSolucao melhorSolucao = valor
Felizmente, existe uma solução pseudo polinomial para o problema. Suponha que temos n objetos, sendo que o i-ésimo objeto tem valor v[i] e peso p[i]. Podemos usar uma estrutura recursiva para resolver o problema da mochila booleana por programação dinâmica. A ideia é guardar em uma tabela (mochila) as soluções das (sub)instâncias do problema. A tabela é definida como:
mochila[# de objetos][capacidadeMáximaMochila] = maior valor alcançado com uma mochila de capacidade capacidadeMáximaMochila e itens 1,...,# de objetos
Lembrando que ou um item é necessário para alcançar o valor ótimo, ou não é, então podemos expressar o valor dos elementos de nossa tabela como:
mochila[i][peso] = max( mochila[i-1][peso], //o elemento i não é usado pela solução ótima v[i] + mochila[i-1][peso-p[i]] //o elemento i é usado pela solução ótima ) como condição de contorno caso p[i] > peso => mochila[i][peso] = mochila[i-1][peso]
Observe que essa solução tem complexidade O(# de objetos * capacidadeMáximaMochila). Mas, anteriormente eu não afirmei que o problema da mochila é NP-completo? Se você ficou curioso a esse respeito aqui e aqui você poderá encontrar a justificativa.
Dei aqui apenas uma explicação superficial sobre o problema da mochila, se você não o conhecia e achou interessante uma ótima referência para uma leitura mais aprofundada é o livro do Cormen (Introduction to Algorithms).
Olá meus amigos nerds, hoje iremos ajudar nosso amigo Mário a resolver seus problemas. Não me pergunte, que Mário? Pois, não resistirei fazer aquela piadinha infame, ainda mais que o problema de hoje fala de armários.
O problema 1890. Mário nos pede para ajudar nosso amigo Mário a organizar seus armários, de modo a atender de melhor seus clientes. Mais especificamente, dado um conjunto de armários livres e numerados (e com rodinhas) nos é pedido que calcule qual é o menor número de movimentações de armários que deve ser feito para que esses armários livres sejam dispostos de modo a haver n armários livres em sequência.
Solução
Esse é um problema interessante, pois a princípio ele parece bem difícil, mas na realidade é fácil. Observe, inicialmente, que o número de movimentos (trocas) necessários para dispor n armários vazios em sequência é menor que n (pelo menos um armário vazio já estará no lugar). Observe ainda, que a sequência de armários vazios necessariamente começará em um dos L armários (obvio). Se decidirmos começar nossa sequência de armários a partir do armário i, teremos que trocar de posição todos os armários ocupados a partir de i até (i+n). Assim, se contarmos quantos armários ocupados existem a partir de cada i em L e escolhermos o menor desses números teremos nossa resposta. Essa é precisamente a ideia do algoritmo abaixo, onde contamos o número de armários desocupados (que é complementar ao número de armários ocupados) uma vez que essa é a informação que a entrada do problema nos fornece.
maiorNumArmariosDesocupados = 0
for i in (L-n) //L-n é a última posição em que eu posso iniciar uma sequência de n armários
Seja x o número de armários desocupados existentes dentro da janela [i, i+n] if x > maiorNumArmariosDesocupados maiorNumArmariosDesocupados = x
numTrocas = n - maiorNumArmariosDesocupados
Implementação
Observe que em minha implementação eu armazeno apenas as posições dos armários vazios. Isso me permite otimizar um pouco o meu for.
Olá meus amigos nerds, em primeiro lugar desculpem-me por meu hiato, na última semana estive trabalhando, juntamente com alguns amigos, em um sistema de recomendação de problemas para o spoj e acabei ficando sem tempo de conversar com vocês.
Hoje vamos contar quantas ligações faz um atendente de telemarketing, já que é isso que o problema 19960. Telemarketing nos pede.
O problema nos fornece uma lista de ligações que devem ser feitas na ordem fornecida, juntamente com o tempo necessário para se fazer cada ligação e nos pede que contemos quantas ligações cada um dos n atendentes de telemarketing devem fazer.
Solução
Lendo o problema, é possível perceber que para saber quantas ligações cada atendente fez é necessário simularmos as ligações feitas. O problema então reside em fazer essa simulação de modo eficiente.
Uma forma simples de simularmos as ligações é simularmos o que ocorre em cada instante de tempo, obviamente simular cada instante de tempo além de ser desnecessário é muito custoso. Felizmente, podemos restringir nossa simulação a dois momentos:
inicio de uma ligação - momento que um vendedor se torna indisponível
fim de uma ligação - momento em que um vendedor se torna ocioso
O seguinte algoritmo realiza a simulação, onde uma fila de prioridades é usada para manter de modo eficiente qual será o próximo vendedor ocioso (e portanto o responsável por fazer a ligação)
Seja Ti o tempo gasto em ligações pelo vendedor i. para cada vendedor Ti = 0 Adicione cada vendedor a fila de prioridade f, ordenada pelo tempo Ti para cada ligação Seja v o vendedor que está no topo da fila Esse vendedor realiza essa ligação (incremente o número de ligações que ele fez) Seja Tl o tempo da ligação Ti += Tl
Esse tipo de simulação apresentada no algoritmo acima é conhecida como simulação de eventos discretos (você pode saber mais sobre ela aqui).
Implementação
Observe que usei apenas inteiros nessa simulação, já que 30*1.000.000 cabe em 32 bits (int).
