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