"Saving the Universe" foi o primeiro problema da etapa de classificação (
Qualification Round) do Google Code Jam 2008. Discuto aqui o problema e a minha solução.
O meu
post anterior contém um resumo do que é o Google Code Jam. Para ver as regras e o problema completo, veja o
site oficial.
Talvez por ser o primeiro da lista, mas principalmente por parecer o mais fácil, este foi o problema que recebeu o maior número de tentativas. Entretanto, ele tem as suas pegadinhas, o que fez com que tivesse a menor taxa de acertos para o "small input".
Descrição do ProblemaEste é um daqueles problemas que exigem a interpretação do enunciado e a coragem de assumir algumas premissas. É uma brincadeira em cima de uma lenda urbana que diz que o universo implodirá se alguem pesquisar por 'google' no Google. Limpando o enunciado e olhando com atenção os exemplos fornecidos, ficamos com algo assim:
- A primeira linha da entrada contém o número de casos de teste (N).
- Cada caso começa com uma linha contendo o número de máquinas de busca (S). As S linhas seguintes contém os nomes destas máquinas de busca. Em seguida vem uma linha com o número de consultas (Q), as Q linhas seguintes contém as consultas, que são os nomes das máquinas de busca.
- O objetivo do programa é direcionar as consultas para as máquinas de busca, na ordem de entrada, reduzindo o número de mudanças de máquina e evitando enviar para uma máquina uma consulta com o seu nome. Para isto o programa pode buferizar as consultas antes de enviá-las para a máquina de busca (algo que está implícito nos exemplos mas não explícito no enunciado).
- A saída do programa para cada caso é o número de mudanças de máquina de busca necessárias.
Resolvendo o ProblemaUma vez entendido o funcionamento desejado, fica claro que é uma questão de buferizar as consultas até que não se consiga mais atendê-las sem mudar de máquina de busca. Em outra palavras, quando o nome de todas as máquinas de busca apareceu nas consultas é hora de mudar.
Usando um exemplo simples. Supondo que as máquinas de busca sejam A B e C e as consultas sejam A A B A B C C A A A B C:
- o primeiro 'lote' de consultas é A A B A B
- ao ler o C é preciso fechar o primeiro lote
- o segundo 'lote' é C C A A A
- ao ler o B fechamos o segundo lote
- o último 'lote' seria B C
- o resultado são 2 mudanças de máquina de busca
Implementado a SoluçãoPensei em duas formas de implementar a solução:
- Ir montando os 'lotes' à medida em que ler as consultas. Quando o tamanho do lote ultrapassa de S-1 é hora de chavear e iniciar um novo lote. Com isto eu poderia ignorar a lista dos nomes das máquinas de busca. Por outro lado, cada consulta lida exige uma busca no lote atual para ver se é um nome novo.
- Procurar cada consulta lida na lista de máquinas de busca, convertendo-a assim em um índice. Usar este índice para ir 'ticando' as novas e manter um contador de máquinas disponíveis. Quando o contador for baixar de 1 para 0 é hora de chavear.
Acabei adotando a segunda opção por achá-la mais otimizada, além de funcionar corretamente se por acaso uma das consultas não for um nome de máquina de busca. Optei por ordenar a lista de máquinas de busca usando inserção simples para depois fazer buscas binárias. Estes dois algorítmos são bem simples e eu estava confiante em conseguir codificá-los sem erro (o que realmente aconteceu).
Nota: nestes concursos normalmente a melhor opção é sempre usar o algorítmo mais simples que tenha o desempenho desejado. No caso do Code Jam as linguagens e bibliotecas são livres, portanto seria uma vantagem usar uma linguagem que já tivesse pronta estruturas apropriadas para montar a lista e fazer a busca (como C++, Java, C#, etc). Mas não seria tão divertido e gratificante...
O meu CódigoO código completo pode ser baixado do
scoreboard do Code Jam (lá na posição 1117), reproduzo abaixo apenas as partes interessantes, sem os códigos de depuração e os comentários redundantes. O código foi feito com o Microsoft Visual C++ v6, mas deve rodar em outros ambientes. Os comentários e identificadores estão me inglês (como é tradição na produção científica brasileira*).
O loop básico para tratar os "N" casos (comum para todos os problemas) é óbvio:
scanf ("%d", &nCases);
for (iCase = 1; iCase <= nCases; iCase++)
{
// ... trata um caso
printf ("Case #%d: %d\n", iCase, nSwitches);
}O tratamente de um caso ficou assim:
for (nS = 0; nS < S; nS++)
{
gets (name);
InsertEngine (name);
}
nSwitches = 0;
unused = nS;
memset (used, ' ', MAX_ENGINES);
scanf ("%d\n", &Q);
for (nQ = 0; nQ < Q; nQ++)
{
gets (name);
se = FindEngine (name);
if (se != -1)
{
if (used[se] == ' ')
{
if (unused == 1)
{
// must switch
nSwitches++;
unused = nS;
memset (used, ' ', MAX_ENGINES);
}
used[se] = '*';
unused--;
}
}
}
Reparar que usei um array de caracteres para marcar as máquinas usadas e não usadas com '*' e ' '. Embora o código acima seja simples, consegui fazer uma besteira e o resultado foi um erro na primeira tentativa de tratar um 'small input'.
A inserção na lista ordenada de máquinas de busca ficou:
void InsertEngine (char *name)
{
int i;
strcpy (Engines[nS], name);
for (i = nS; i > 0; i--)
if (strcmp (Engines[order[i-1]], name) <= 0)
break;
if (i < nS)
memmove (order+i+1, order+i, (nS-i)*sizeof(int));
order[i] = nS;
}
Por último, a minha velha amiga busca binária:
int FindEngine (char *name)
{
int first, last, mid, dif;
first = 0;
last = nS-1;
while (last >= first)
{
mid = (last+first)/2;
dif = strcmp (Engines[order[mid]], name);
if (dif == 0)
return mid;
else if (dif < 0)
first = mid + 1;
else
last = mid - 1;
}
return -1; // not found
}
*
Isto vem de um 'causo' contado pelo brilhante físico Richard Feynman. Para uma visita ao Brasil ele preparou uma apresentação em português (Feynman gostava de estudar linguas). Entetanto, todas as apresentações anteriores no evento foram em inglês, o que o levou a se 'desculpar' por desconhecer esta 'tradição' brasileira. Após a apresentação (em português) de Feynman, todos os oradores seguintes apresentaram seu trabalhos também em português.
