Google Code Jam 2008 - Crop Triangles

Crop Triangles foi o primeiro problema da rodada 1B do Google Code Jam. Embora fosse considerado um problema fácil, pouco mais de um terço dos que enviaram um solução para o large input conseguiram acertar.

O enunciado é bastante enrolado e um exame atento dos exemplos é necessário para entender o que é desejado. Tirando as enrolações, ficamos com o seguinte:

Tem-se uma sequência de N pontos de ccordenada (x,y) gerada pelo seguinte trecho em C:

x = x0;
Y = y0;
for (i = 1; i < n-1; i++)
{
 x = (A * x + B) % M;
 y = (C * y + D) % M;
}

onde n, x0, y0, A, B, C, D e M são inteiros que variam para cada caso a ser tratado.

O resultado desejado é o número de trios de pontos distintos que tenham a soma dos x e a soma dos y múltiplas de 3.

Pegando o exemplo oficial, com n=4, A=10, B=7, C=1, D=2, x0=0, y0=1 e M=20, temos:

• os pontos gerados são (0,1), (7,3), (17,5) e (17,7)
• o único trio que atende à condição estipulada é (0,1) (7,3) (17,5).

Tão importante quanto o enunciado são os limites:

• número máximo de casos: 10
• 0 <= A, B, C, D, x0, y0 <= 10^9
• 1 <= M <= 10^9
• número máximo de pontos: 100 no small input e 100.000 no large input

Um primeiro fato a lembrar é que um unsigned nos compiladores habituais de 32bits suporta números até 4*1024^3 (ou aproximadamente 4*10^9). Portanto um unsigned é suficiente para os valores, mas não para o cálculo entre eles (A*x ou A*y pode passar de 32bits). Na hora, eu lembrei da primeira parte, mas não da segunda : (.

O segundo fato é que para 100 pontos uma solução força bruta, testando todas as combinações, é viável; para 100.000 pontos vai estourar o tempo.

Solução Força Bruta

A solução força bruta é trivial (exceto para quem esquecer do overflow, como eu):

_int64 n, x0, y0, A, B, C, D, M;

#define MAX_PONTOS 100

struct
{
 int x, y;
} Ponto [MAX_PONTOS];

void GeraPontos (void)
{
  int i;
  int x, y;

  x = (int) x0;
  y = (int) y0;
  for (i = 0; i < n; i++)
  {
    Ponto[i].x = x;
    Ponto[i].y = y;
    x = (int) ((A * (_int64) x + B) % M);
    y = (int) ((C * (_int64) y + D) % M);
  }
}

int ContaTrios (void)
{
  int trios = 0;

  int i, j, k;

  for (i = 0; i < n; i++)
    for (j = i+1; j < n; j++)
      for (k = j+1; k < n; k++)
      {
        if ((((Ponto[i].x + Ponto[j].x + Ponto[k].x) % 3) == 0) &&
            (((Ponto[i].y + Ponto[j].y + Ponto[k].y) % 3) == 0))
        {
          trios++;
        }
      }

  return trios;
}

Solução Inteligente

O primeiro ponto a reparar é que não estamos interessados no valor da soma, mas sim no resto da divisão da soma por 3. Portanto tanto faz se o x de um ponto é 1, 4, 7 ou qualquer valor com resto 1, a contribuição para a decisão vai ser a mesma.

O pulo do gato é perceber que uma vez que coordenadas com mesmo resto são iguais, basta contar as ocorrências dos restos, não é preciso guardar as coordenadas:

int cont[3][3];

void GeraPontos (void)
{
  int i;
  int x, y;

  cont[0][0] = cont[0][1] = cont[0][2] = 0;
  cont[1][0] = cont[1][1] = cont[1][2] = 0;
  cont[2][0] = cont[2][1] = cont[2][2] = 0;

  x = (int) x0;
  y = (int) y0;
  for (i = 0; i < n; i++)
  {
    cont[x %3][y %3]++;
    x = (int) ((A * (_int64) x + B) % M);
    y = (int) ((C * (_int64) y + D) % M);
  }
}

Montada a tabela de contagem de restos, fica rápido contar os totais. É uma questão de determinar quais combinações produzem soma com resto zero.

Por exemplo, é claro que todas as combinações cont[0][0]*cont[1][1]*cont[2][2] resultam em resto zero. Se pegamos mais de um ponto do mesmo grupo, é preciso fazer o desconto correspondente. Por exemplo, as combinações de três pontos diferentes que tem resto zero nas duas coordenadas é cont[0][0]*(cont[0][0]-1)*(cont[0][0]-2)/6. Adaptando o código java do primeiro colocado (mystic):

__int64 ContaTrios (void)
{
  __int64 trios = 0;
  int i, j, k;
  __int64 ci, cj, ck;

  for (i = 0; i < 9; i++)
    for (j = i; j < 9; j++)
      for (k = j; k < 9; k++) 
      {
        if (((i/3+j/3+k/3) % 3 == 0) &&
            ((i%3+j%3+k%3) % 3 == 0))
        {
           ci = cont[i/3][i%3];
           cj = cont[j/3][j%3];
           ck = cont[k/3][k%3];
           if (i < j && j < k)
             trios += ci*cj*ck;
           else if (i == j && j < k)
             trios += (ci * (cj - 1) * ck) / 2;
           else if (i [ j && j == k)
             trios += (ci * cj * (ck - 1)) / 2;
           else
             trios += (ci * (cj - 1) * (ck - 2)) / 6;
        }
      }

  return trios;
}

Reparar que novamente o int não é suficiente para armazenar o resultado.