PRACAALI - Praça de alimentação

Olá meus amigos nerds! Hoje vamos resolver o problema PRACAALI - Praça de alimentação pedido pelo nosso amigo Jonas. Mais especificamente, o problema pede para estimar a quantidade máxima de pessoas que podem ter estado dentro de uma cantina, dados os horários de entrada e saída de cada pessoa.

Solução

Esse é um problema difícil, levei um bom tempo para resolver. Quando nos deparamos com um problema assim, a primeira coisa a fazer é tentar resolver uma versão mais fácil do problema. E é assim que vamos resolver esse problema hoje.

Caso não houvessem ? o problema poderia ser modelado como um problema de soma máxima em vetores. Pense que cada pessoa que entra adiciona +1 a soma de pessoas dentro da cantina e cada pessoa que sai -1 a tal soma. Assim, se ordenássemos os eventos de entrada e saída pela hora que eles aconteceram e aplicarmos o algoritmo de soma máxima encontraríamos o número máximo de pessoas dentro da cantina.

Como queremos o número máximo possível de pessoas que poderiam estar na cantina, podemos dispor das ? da forma que quisermos. Então nosso problema se torna em tentar descobrir a atribuição correta de entrada/saída para cada ?.

Vamos começar descobrindo o número de interrogações que temos que transformar em entradas. Sejam num_e o número de eventos de entrada dados na instância do problema, num_s o número de eventos de saída e num_x o número de eventos incertos (?). É garantido pelo enunciado que a entrada do problema é coerente. Ou seja, metade de todos os eventos, mesmo os ?, são de entrada e metade de saída. Além disso, todo evento de saída é correspondente a um evento anterior de entrada.

Vamos estimar o número máximo de eventos ? que podem ser de entrada. Temos dois casos a considerar.

Se num_e > num_s: sabemos que, dos num_x eventos ?, (num_e - num_s) são de saída, para compensar a falta de eventos de saída na entrada. Do restante, metade será de entrada e metade de saída.

Por outro lado, se num_s > num_e, sabemos que (num_s - num_e) eventos ? deverão ser de entrada correspondente aos eventos de saída sobrando.

De forma mais algorítmica, o número máximo de eventos ? que necessariamente tem que ser eventos de entrada (max_entradas) seria:

num_x = total_eventos - (num_s + num_e)
if num_e > num_s
    max_entradas = (num_x - (num_e - num_s)) / 2
else
    max_entradas = num_s - num_e + (num_x - (num_s - num_e)) / 2

 

A grande sacada para resolver esse problema é ver que podemos atribuir os primeiros max_entradas eventos ? como sendo eventos de entrada. A prova de que este algoritmo guloso funciona será por contradição. Vamos supor que exista outra solução e mostrar que nossa solução não será pior que essa outra solução. Para isso, vamos partir da nossa solução e trocar eventos de posição e ver o que acontece

Vamos chamar de período o espaço entre dois eventos correspondentes a uma mesma pessoa, relativo à sua entrada. Ou seja, o período de uma pessoa é o tempo entre seus eventos de entrada e saída. Note que o período depende do horário de entrada.

Suponha uma solução ótima diferente da gerada pelo nosso algoritmo. Consideremos nesta outra solução as duas primeiras pessoas a entrar no local que tenham período diferente da nossa solução. Nosso algoritmo, obviamente, classificaria os 4 eventos, em ordem, como EESS (onde E é entrada e S é saída). Uma solução válida diferente da nossa só pode ser ESES; caso contrário, ela seria incoerente (dado que as pessoas que entraram antes têm eventos coerentes associados a elas). Assim, temos três casos possíveis: ou o momento em que o maior número de pessoas estava no restaurante foi entre os dois primeiros eventos, ou entre o segundo e o terceiro, ou entre os dois últimos (E*E*S*S os momentos são os *). Transformando esta suposta solução ótima na nossa solução (ou seja, trocando o tipo dos dois eventos do meio), obtemos uma solução melhor que essa solução ótima (o número de pessoas no restaurante entre os dois primeiros e entre os dois últimos eventos permanece o mesmo, enquanto o número de pessoas entre os eventos do meio foi aumentado em 1). A partir de sucessivas transformações deste tipo, podemos transformar qualquer solução ótima, sem piorá-la, na solução dada pelo nosso algoritmo. Portanto, esta deve, necessariamente, ser ótima.

Então a solução final para o problema é supor que os primeiros num_entradas eventos ? são de entrada e os outros de saída e aplicar o algorítimo da soma máxima de vetores no array resultante.

Implementação

 

18550. Troco

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.

1389. Pedido de Desculpas

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).

Implementação

12930. Pizza

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.

Implementação

2836. Moedas

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.

Implementação