quarta-feira, maio 11, 2011

Google Code Jam 2011: QR_C - Candy Splitting

No terceiro problema da rodada de qualificação a coisa esquenta. Parece ser um problema de maximização que requer uma solução a base de programação dinâmica - mas será isto mesmo?

Quando eu finalmente enxerguei a solução soltei um palavrão em voz alta...

O Problema

O enunciado oficial pode ser lido aqui. Resumindo, temos um conjunto de itens (doces) com valores associados que deve ser dividido em dois grupos, de forma que a "soma binária sem vai-um" dos valores dos dois grupos seja iguais e que a diferença entre a "soma aritmética" dos dois grupos seja a maior possível.

A saída do programa deve indicar se é possível fazer esta divisão e, se sim, qual a maior "soma aritmética" que pode ser conseguida.

Minha Solução

Uma vantagem que tive é que imediatamente reconheci a tal "soma binária sem vai-um" como sendo o meu velho amigo ou-exclusivo (xor). Esta lembrança vem de quando comecei a aprender eletrônica digital. Para não haver dúvidas, o enunciado apresentava um exemplo que mostrava a "tabela verdade" da operação.

Minha primeira impressão é que era uma variação do problema da Soma de Sub-Conjuntos, e gastei um bom tempo tentando implementar antes de concluir que não era por aí.

Após perambular um pouco me veio um "momento Eureka": dois números são iguais se e somente se o ou-exclusivo deles for zero. Portanto para saber se a divisão era possível ou não bastava fazer o xor de todos os números e testar se o resultado era zero. Rabisquei então uma equação do tipo

C1 xor C2 xor C3 ... xor Cn = 0

onde os Ci são os valores dos itens. O meu problema era como repartir os itens em dois grupos para que o xor dos itens de um grupo fosse igual ao xor dos itens do outro grupo... espera aí, isto quer dizer que o xor deve ser zero:

(Ca xor Cb xor ...) xor (Cx xor Cy ...) = 0

como o xor tem as propriedades comutativa e associativa, esta equação é a mesma que a anterior! Em outras palavras, se a divisão é possível, você pode separar os itens como quiser.

Aí fica fácil tira o doce da mão da criança: damos para ela o item de menor valor e ficamos com o resto.

Só para constar segue a implementação em C:
int c [1000];

void main (void)
{
int iCase, nCases;
int i, n, total, sum, min;

scanf ("%d\n", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
scanf ("%d\n", &n);
total = sum = 0;
min = 1000001;
for (i = 0; i < n; i++)
{
scanf ("%d ", &c[i]);
total ^= c[i];
sum += c[i];
if (c[i] < min)
min = c[i];
}
if (total != 0)
printf ("Case #%d: NO\n", iCase);
else
printf ("Case #%d: %d\n", iCase, sum - min);
}
}

Nenhum comentário: