quarta-feira, agosto 06, 2008

Google Code Jam 2008 - Triangle Areas

Triangle Areas foi o segundo problema da 2a rodada on-line do Code Jam 2008. Fiquei a maior parte das duas horas da competição tentando resolvê-lo sem sucesso. Curioso, baixei as soluções dos dois primeiros colocados e me assustei com a simplicidade delas. Duas perguntas me surgiram: como eles chegaram nesta solução e como garantir que elas estão corretas. Após quase quatro dias de ruminações, a luz surgiu hoje enquanto vazia a barba.

O Problema

Raspando o problema à sua essência, são dados três números inteiros N, M e A, maiores que zero. O problema consiste em achar um triângulo (xa,ya), (xb,yb), (xc,yb) cuja área seja A/2 com x e y inteiros e 0 ≤ x ≤ N e 0 ≤ y ≤ M (ou indicar que o problema é impossível).
A Solução

A fórmula para a área de um triângulo a partir das coordenadas dos pontos que o compõe é:

|xa*yc - xa*yb + xb*ya - xb*yc + xc*yb - xc*ya|/2

É claro que os casos de teste eram grande o suficiente para tornar inviável o teste de todas as combinações por força bruta. É preciso, portanto, simplificar.

Se assumirmos que o ponto a é a origem (0,0) a fórmula se simplifica para:

|xc*yb - xb*yc|/2

Ainda assim são valores demais para a força bruta. Vamos tentar simplificar um pouco mais e assumir que xb e yc são zero, fazendo um triângulo retângulo encostado nas bordas:
Neste caso ficamos com xc*yb = A. Ou seja, precisamos quebrar A em dois fatores. Dá para perceber que um A primo e maior que N e M estraga a brincadeira (por exemplo, se N=2 e M=6 não conseguimos achar um triângulo com A=7). Simplificamos demais.

Vamos tentar fazer xb =1. Ficamos com |xc*yb - yc| = A. Será que isto resolve?

Em primeiro lugar, é óbvio que se A for maior que N*M o problema é impossível (se você não perceber isto pelas fórmulas, considere que temos um retângulo de área N*M e que o maior triângulo que conseguimos colocar nele terá área N*M/2).

A questão é: para qualquer valor de A maior que zero e menor ou igual a N*M conseguimos achar xc, yb e yc que atendam à nossa fórmula? A resposta é sim. O segredo é reparar que a fórmula se assemelha muito a uma divisão de inteiros (exceto pelo '-' ou invés de '+'): podemos considerar que xc é o quociente da divisão de A por yb e yc é uma espécie de resto.

A coisa fica mais clara se forçarmos yb = M. Ficamos com |xc*M - yc| = A. Variando xc de 1 a N e yc de 0 a M-1 conseguimos todos os valores de 1 a N*M.

O Código

Resolvido o problema, o código é incrivelmente trivial:
#include 

void main (void)
{
int iCase, nCases;
int N, M, A, xc;

scanf ("%d", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
scanf ("%d %d %d", &N, &M, &A);
if (A > N*M)
printf ("Case #%d: IMPOSSIBLE\n", iCase);
else if ((A % M) == 0)
printf ("Case #%d: 0 0 1 %d %d 0\n", iCase, M, A/M);
else
{
xc = (A/M)+1;
printf ("Case #%d: 0 0 1 %d %d %d\n", iCase, M, xc, xc*M - A);
}
}
}
Pena que não tive a capacidade e frieza de achar esta solução durante a competição...

2 comentários:

Anônimo disse...

Ola DQ!!!

Nao sei se você se lembra de mim, amigo do Wanderley Caloni e eu estava com vocês no 2o encontro de C++... :)

Enfim, esse ano eu não participei do Codejam, porem ouvi ótimos comentários sobre o formato... bons sites para treinamento, não sei se você já conhece são o http://www.spoj.pl, inclusive tem uma versão brasileira http://br.spoj.pl e o site do UVA (universidade de valladoid) http://icpcres.ecs.baylor.edu/onlinejudge/

Com esses, acredito que já da para pegar bastante o jeito e treinar para o ano que vem!!! :D

Daniel Quadros disse...

Olá, Alan

Eu conhecia o UVA mas eu realmente não treinei nada antes de competir. Para o ano que vem vou tentar me preparar, já comprei alguns quilos de livros. Após estudar um pouco vou começar a frequentar os sites de treinamento.

[]