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 BrutaA 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;
}
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.