terça-feira, junho 15, 2010

Google Code jam 2010: Load Testing

Load Testing (teste de carga) foi o segundo problema da rodada 1C. Uma distração minha neste problema me impediu de obter a pontuação máxima na rodada.

O enunciado (que você encontra aqui) parece confuso na primeira leitura; felizmente os exemplos são mais claros. Tentando colocar de uma forma simples:
  • Você precisa determinar qual o número mínimo de testes de carga a serem feitos em um site.
  • Os testes são concluídos quando sabemos que o site suporta, dentro de um fator C, pelo menos P participantes ou uma quantidade X < P
  • Suportar X participantes dentro de um fator C significa que você sabe que o site suporta uma carga a mas não uma carga a*C com a < P < a*C
  • Inicialmente você sabe que o sistema suporta uma carga L mas não uma carga P.


Vamos considerar um dos exemplos do problema, no qual C=2, P=97 e L=24. Inicialmente sabemos que o site suporta até 47 participantes com fator 2 (pois 47 é o menor número menor que 2*24). Para termos certeza que o site suporta pelo menos 97 participantes com fator 2, precisamos testar com 49 (o menor número que multiplicado por 2 é maior que 97). Entretanto, se este teste for mal sucedido ainda não saberemos se o site suporta ou não 48 participantes. São precisos, portanto, dois testes.

Este exemplo sugere que os melhores pontos para teste são L*C, L*C*C, L*C*C*C, etc. É intuitivo que devemos primeiro tentar "no meio do caminho", usando um esquema parecido com a busca binária. Se L*C^(n-1) < P <= L*C^n, são precisos fazer, no pior caso, r = log2(n) (arredondado para cima se não for exato) casos.

Se ainda não ficou claro, veja a explicação oficial aqui.

A minha solução abaixo determina n e r "na marra". O meu erro na competição foi não reparar que L*C^n pode não caber em um inteiro de 32 bits. Na versão abaixo estou usando inteiro de 64 bits (o long long).
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void main (void)
{
int iCase, nCases;
int L, P, C;
int n, r;
long long prod;

scanf ("%d\n", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
scanf ("%d %d %d\n", &L, &P, &C);

prod = L;
n = 0;
while (prod < (long long) P)
{
prod *= C;
n++;
}
r = 0;
prod = 1;
while ((long long) n > prod)
{
prod = prod << 1;
r++;
}

printf ("Case #%d: %d\n", iCase, r);
}
}

Nenhum comentário: