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:

view plaincopy to clipboardprint?

1. int c [1000];  
2.   
3. void main (void)  
4. {  
5.  int iCase, nCases;  
6.     int i, n, total, sum, min;  
7.   
8.  scanf ("%d\n", &nCases);  
9.  for (iCase = 1; iCase <= nCases; iCase++)  
10.  {  
11.      scanf ("%d\n", &n);  
12.         total = sum = 0;  
13.         min = 1000001;  
14.         for (i = 0; i < n; i++)  
15.         {  
16.             scanf ("%d ", &c[i]);  
17.             total ^= c[i];  
18.             sum += c[i];  
19.             if (c[i] < min)  
20.                 min = c[i];  
21.         }  
22.         if (total != 0)  
23.             printf ("Case #%d: NO\n", iCase);  
24.         else  
25.             printf ("Case #%d: %d\n", iCase, sum - min);  
26.  }  
27. }  

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);
 }
}