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, como é costume, estou aqui hoje para resolver nosso problema da semana. Infelizmente, o problema que vamos resolver é muito fácil, mas como nosso objetivo é resolver todos os problemas do spoj isso não importa muito. Não é mesmo?
Hoje vamos somar números, já que é isso que o problemas 3830. Soma nos pede para fazer. Mais especificamente, esse problema nos pede que, dada uma lista de N inteiros, encontre a soma de todos eles.
Fácil não, um simples for resolve...
Vamos brincar um pouco mais? Será que é possível resolver esse problema se a tecla + do seu computador estivesse estragada? Certamente que sim, e é o que eu vou mostrar agora.
Modelagem
O segredo para resolver esse problema é lembrar que soma e subtração podem ser feitas usando se operações lógicas. Vamos dividir o nosso problema de somar em dois problemas:
Somar sem considerar o vai 1
Calcular e somar o vai 1
Vamos tentar somar dois números de 1 bit sem considerar o vai 1. Sejam a e b esses números:
a b a+b sem vai 1 1 1 0 1 0 1 0 1 1 0 0 0
É possível perceber que o resultado a+b é igual a 1 quando ou exclusivamente a ou ou exclusivamente b forem 1. Assim a soma sem se considerar o vai 1 pode ser feita como a xor b.
Calcular o vai 1 pode ser feito da mesma forma:
a b vai 1 1 1 1 1 0 0 0 1 0 0 0 0
Ou seja o vai 1 pode ser representado como a and b.
Pronto agora é só somar o a+b sem vai 1 com o vai 1.Opa, mas voltamos ao mesmo problema de antes. Para contornar esse empecilho, podemos usar recursão, como feito no pseudocódigo abaixo.
soma_recursivo(a, b) if (b == 0) return a //condição de parada somaSemVai1 = a xor b vai1 = a and b vai1 = vai1<<1 //o vai 1 sempre deve ser somado ao próximo bit return soma_recursivo(somaSemVai1, vai1)
Olá meus amigos nerds, hoje estou aqui para falar de problemas do mundo real, que vocês podem ter que lidar quando estiverem desenvolvendo algum sistema de grande porte.
Outro dia eu precisava fazer uma atualização em algumas tabelas de um banco de dados, para acomodar algumas melhorias em um dos sistemas que eu ajudo a desenvolver.
Eu tinha a opção de gerar o sql de atualização na unha ou usar o Hibernate para isso. Como a atualização não era simples, optei por fazê-la usando o Hibernate (sou preguiçoso como todo bom cientista da computação)
(Se você não conhece o Hibernate, ele é um framework muito útil para desenvolvimento de aplicações (java) que precisam se comunicar com bancos de dados relacionais. A grosso modo, ele faz o mapeamento dos objetos da sua aplicação para as tabelas do seu banco de dados, gerando para você o sql das consultas de modo transparente.)
Você deve estar se perguntando qual o problema. Isso qualquer peão programador consegue fazer. O problema estava no número de objetos (linhas das tabelas) que eu tinha que atualizar (alguns milhares). É claro que, como um bom nerd, eu estava atento a esse fato. E para evitar problemas de memória, eu havia implementado meu código de modo a fazer a atualização de forma paginada, ou seja, eu carregava apenas uma parte dos objetos a serem atualizados de cada vez na memória.
Testei meu código usando um dump do banco de dados e para minha surpresa ele começou a demorar muito a executar. Meu instinto nerd me dizia, deu merda! Então eu voltei ao código e o instrumentei (adicionei informações de tempo ao log da execução) de modo a obter informações de onde estava o problema. Eis que encontrei o seguinte comportamento:
Tempo de execução do método de atualização sobre a 1ª página de dados 1s
Tempo de execução do método de atualização sobre a 2ª página de dados 2s
Tempo de execução do método de atualização sobre a 3ª página de dados 4s
Tempo de execução do método de atualização sobre a 4ª página de dados 6s
...
Você é capaz de me dizer onde está o problema? Tanto o tamanho das páginas, quanto a natureza dos dados que o método de atualização lidava não mudavam. Sendo assim, o tempo de execução de uma página deveria ser mais ou menos constante. Então como explicar esse resultado? Além do mais, não poderia ser problema de paginação de memória, já que eu havia tomado esse cuidado de antemão. Correto? Então o que poderia ser?
Minha análize do problema me dizia: isso cheira a problema de memória! Para confirmar ou refutar essa hipótese, verifiquei o consumo de memória do java. Estava mais alto do que seria esperado! Era problema de memória. Mas não deveria ser meu código que o está causando o problema, pois eu havia sido cuidadoso, inclusive eu havia incluído instruções de flush para garantir que eu teria apenas os dados de uma página na memória.
Então formulei a seguinte hipótese: O Hibernate esta se tornando mais lento ao executar uma página, pois ele não deve estar fazendo o flush dos objetos já atualizados. Para confirmar ou refutar essa hipótese, recorri ao google e pesquisei o comportamento do Hibernate. Eis que em algum site eu encontrei a informação de que se você der um flush no Hibernate, fica a critério dele liberar memória ou não! Se eu quisesse forçar o Hibernate a fazer o flush e limpar sua memória interna eu deveria usar o método session.clear().
Adicionei uma chamada a session.clear(), testei novamente meu atualizador e voilá. Problema resolvido!
Lembra da primeira execução do meu atualizador, pois é, ela ainda estava rodando quando terminei de resolver o problema. Ela gastou no final das contas uma hora e pouco para executar, enquanto a versão corrigida gastou menos de um minuto. (Deixei terminar de executar só para poder me gabar depois do speedup da alteração que eu fiz no código do meu atualizador :P)
A lição que fica aqui é que você sempre deve conhecer a arquitetura interna dos frameworks, bibliotecas, etc, que você usa. Esse conhecimento salva vidas e te poupa muita dor de cabeça.
P.S.: Observe que em nenhum momento eu saí colocando breakpoints no meu código e dando step in ou step out em algum debuger visual. A técnica de debug que eu usei para resolver esse problema (de fazer suposições, colher dados e rejeitar ou confirmar as suposições até encontrar o bug) é muito útil na solução de diversos problemas. Em uma outra oportunidade irei falar mais sobre ela.
Olá meus amigos nerds, hoje escolhi resolver um problema especialmente saboroso. Hoje vamos falar de pizza. Já que o problema 12930. Pizza, nos pede para ajudar nosso amigo Rodrigo a escolher o maior número de pedaços de pizza que ele pode comer.
As pizzas de nosso problema tem dois ingredientes, um que Rodrigo gosta (cebola) e outro que ele não gosta (azeitona). Rodrigo deseja pegar fatias consecutivas da pizza de tal forma que estas contenham a maior diferença possível entre as quantidades de cebolas e azeitonas. Para isso, ele contou quantas cebolas e quantas azeitonas haviam em cada fatia e subtraiu os dois valores, nessa ordem. Assim, sempre que uma fatia contiver mais cebolas que azeitonas, ela recebe um número positivo, e caso contrário, um número negativo. Uma fatia cujo número seja zero contém o mesmo número de cebolas e azeitonas. Nossa tarefa nesse problema é maximizar essa diferença com a condição de que Rodrigo pode escolher apenas fatias consecutivas.
Solução
Resolver esse problema de modo eficiente é rasoavelmente difícil. Tão difícil, que eu planejava falar dele na semana passada, mas não consegui resolvê-lo de forma eficiente no tempo que eu dispunha para lidar com ele.
A dificuldade desse problema está no fato da pizza ser circular. Se assim não fosse a solução seria computar a soma máxima (um problema bem clássico de programação dinâmica).
O que nos impede de mapear esse problema para o problema da soma máxima é que não sabemos como escolher o início do array de modo que todos os pedaços de pizza que compõe a soma máxima sejam consecutivos, já que a pizza é circular. Observe o exemplo abaixo:
Na pizza {1, -2, 3} as fatias 3 e 1 são consecutivas, mas não aparecem em elementos consecutivos do array. Se rodarmos o algoritimo da soma máxima sobre esse vetor encontrariamos a soma 3 que é menor que a maior soma possível que é 4 (é só computar a soma máxima desse vetor {-2, 3, 1}, que representa o mesmo vetor circular inicial).
Observe, entretanto, que se conseguirmos adaptar o algoritmo da soma máxima para trabalhar com um vetor circular nosso problema está resolvido.
Uma primeira observação é que, necessariamente há uma fatia que se escolhida como primeiro elemento do array faz com que todos os pedaços pertencentes a soma máxima sejam consecutivos (no exemplo acima basta escolher -2 ou o 3 como início do array). Lembre-se, os pedaços de pizza são consecutivos, o que faz com que eles pareçam não consecutivos é a nossa escolha de como linearizar a pizza.
A escolha de por qual pedaço de pizza começamos nosso array pode ser feita por foça bruta, ou seja, tentando cada pedaço da pizza como sendo o início do array. Isso conduz a uma solução correta para o problema, uma vez que se a soma pedida será a soma máxima de um dos n arrays, mais precisamente, a resposta será a maior das somas máxima. Essa solução tem complexidade quadrática (lembre-se soma máxima pode ser resolvido em O(n) usando-se programação dinâmica). Infelismete, uma solução O(n^2) não é factível para o problema, devido ao tamanho da entrada (10^5^2 é um bocado de tempo).
Então a pergunta é: dá para fazer melhor que isso? Dá sim, abaixo vou mostrar uma solução linear para o problema. E a ideia dessa solução é que não precisamos do passo de força bruta do algoritmo apresentado acima.
Soma máxima em um array circular
Dado um conjunto contendo n números (positivos e negativos) arranjados de forma circular, encontrar a maior soma obtida a partir de elementos consecutivos desse conjunto.
Considere o seguinte array circular {a1, a2, ...,ai,..., aj,..., a(n-1), an}, e suponha que todos os elementos entre ai e aj pertencem a soma máxima. Então a soma máxima nesse vetor será:
ai + a(i+1) + ... + a(j-1) + aj (1)
ou será
aj + a(j+1) + ... + an + a1 + ... + ai (2)
A soma em (1) pode ser obtida usando-se o algoritmo clássico (para um vetor comum) da soma máxima.
A soma em (2), é um pouco mais complicada, mas pode ser calculada da seguinte forma. Seja S a soma de todos os elementos do array. Multiplique todos os elementos do array por -1 (observe que isso não altera o modulo de nenhuma soma, apenas o valor absoluto dela). Sendo assim, se aplicarmos o algoritmo clássico da soma máxima nesse novo vetor teremos como resultado - (a(i+1) + a(i+2) + ... + a(j-1))*. Se da soma de todos os elementos do array original, nós subtrairmos * obteremos a soma (2).
Finalmente, a soma máxima dos elementos do array circular será max((1), (2)).
Uma explicação mais detalhada dessa solução pode ser encontrada aqui.
Olá meus amigos nerds, depois de algumas decepções na última semana, nada melhor que afogar as mágoas resolvendo alguns problemas! E hoje eu trago um problema simples para vocês.
A crescente utilização do transporte aéreo preocupa os especialistas, que prevêem que o congestionamento em aeroportos poderá se tornar um grande problema no futuro. Pensando nisso, o problema 818. Aeroporto nos pede para determinar, a partir de uma listagem de aeroportos e vôos, qual aeroporto possui maior probabilidade de congestionamento no futuro. Como medida da probabilidade de congestionamento o problema usa a soma do número de vôos que chegam e que partem de cada aeroporto. Mais especificamente, o problema pede o identificador do aeroporto que possui maior tráfego aéreo, onde o tráfego é medido pela soma do número de vôos que chegam e que partem do aeroporto.
Modelagem
A simples leitura do problema sugere uma modelagem por grafos. Podemos representar cada aeroporto por um vértice no nosso grafo, assim cada aresta representará um vôo de um aeroporto para outro. Nessa modelagem, o tráfego de cada aeroporto corresponde ao grau do vértice que representa aquele aeroporto. Assim, a resposta para nosso problema é o maior grau dos vértices de nosso grafo.
Computar o grau de cada vértice é bastante simples:
para cada aresta (v1->v2) do grafo
grau_saída[v1]++
grau_entrada[v2]++
Observe que o algoritmo acima funciona mesmo que o grafo tenha arestas paralelas (o que pode ser o caso em nosso problema).
Logo o tráfego em cada aeroporto A será:
trafego[A] = grau_saída[A] + grau_entrada[A]
Assim a resposta do problema será o maior elemento do vetor trafego.
Oi, hoje venho aqui dar uma dica para você que gosta de algoritmos. Segunda passada, começou (novamente) o curso de algoritmos 2 do coursera. Esse curso fala sobre algoritmos gulosos, programação dinâmica, grafos e problemas NP. É um curso muito interessante e vale muito a pena fazer. Experimente!
O Coursera, se você não sabe, é uma plataforma de educação online que oferece cursos de qualidade em várias áreas do conhecimento.
Olá meus amigos nerds, essa semana meus parcos conhecimentos sobre programação dinâmica me permitiram chegar um pouco mais perto de um antigo objetivo meu. E para comemorar, nada melhor que apresentar um problema sobre esse tema!
Hoje vamos discutir o problema 2836. Moedas. Nesse problema, vamos ajudar o rei da Pinelândia a descobrir qual é o número mínimo de moedas que ele precisa juntar para ter um determinado valor. Mais especificamente, dados os valores das moedas disponíveis e um valor que se deseja somar, determinar o número mínimo de moedas que deve ser usado para somar o valor desejado, ou dizer que tal soma é impossível.
Modelagem
Este é um problema clássico de Programação Dinâmica, chamado de Change-making problem, ou Coin Change. Sendo assim não vou falar muito sobre ele.
Vamos começar pelos casos triviais:
Se queremos somar 0 tostões, precisamos de 0 moedas...
Se precisamos somar x tostões e temos uma moeda de x tostões precisamos de uma moeda...
Se precisamos somar x tostões e a moeda de menor valor é maior que x, então o problema é impossível...
Agora vem o truque.
Se precisamos somar y tostões usando uma única moeda de x tostões precisamos ser capazes de juntar moedas no valor de y-x tostões. Assim se formos capazes de determinar o número mínimo de moedas necessárias para juntar y-x tostões nosso problema fica resolvido.
Mais formalmente, sejam m o valor que queremos ajuntar e m1, m2,..,mm os valores das moedas disponíveis, temos:
minimoMoedas(0) = 0
minimoMoedas(m) = 1 se temos uma moeda de m tostões
minimoMoedas(m) = 1 + minimo [minimoMoedas(m-m1), minimoMoedas(m-m2), ...,minimoMoedas(m-mm)]
Basta agora fazermos uma programação dinâmica para calcular minimoMoedas e Voilá, problema resolvido.
