Google Code Jam 2008 - Introdução

O Google Code Jam é uma competição de programação. Decidi participar este ano e apresento aqui alguns comentários a respeito.

Competições de Programação

Existem diversas competições de programação por aí. Uma das mais tradicionais é a ICPC, uma competição para estudantes universitários promovida pela ACM, que aqui no Brasil é a Maratona de Programação. No Brasil temos também a Olimpíada Brasileira de Informática, para alunos do segundo grau. Estes sites possuem arquivos de questões passadas e links para competições on-line.

As questões constam de uma descrição e alguns exemplos de entradas e as saídas corretas correspondentes. Para permitir a correção automatizada das provas, são estipulados formatos rígidos para as entradas e saídas e a conferência é feita na base da comparação dos arquivos de saída com um gabarito.

Um guia sobre como participar destas competições pode ser baixado daqui. O inglês do autor às vezes dá uma falhada e tem um tutorial meio longo de C, mas as dicas são relevantes, mesmo as mais óbvias.

Google Code Jam 2008

Esta competição tem algumas características curiosas. Nos exemplos que mencionei acima, a compilação e execução dos programas é feita pela "banca", o que limita as opções de linguagem e compilador. A competição do Google aceita qualquer linguagem e compilador (e até mesmo soluções à mão!).

A avaliação de cada questão consta de duas partes.

• A primeira ("small input") gera um arquivo de teste pequeno (e mais simples). Após baixar este arquivo o participante tem 4 minutos para enviar o arquivo de saída, que é conferido imediatamente. Em caso de erro (inclusive timeout), o participante pode solicitar vários arquivos (que serão diferentes), mas é penalizado a cada tentativa mal sucedida.
• Na segunda parte ("large input") o aquivo é maior e envolve casos mais complexos. O arquivo de saída deve ser enviado em até 8 minutos e o resultado só é apresentado no final da etapa. Nesta etapa não tem segunda oportunidade.

Nas duas partes os fontes devem ser enviados junto com os arquivos de saída e ficam à disposição para download por todos ao final da etapa.

Qualification Round

A competição terá várias etapas (detalhes no site). A primeira, que acaba de ser concluída, foi relativamente "leve". Foram três questões, disponíveis por 24h. Para passar para a fase seguinte bastava acertar pelo menos um small input e um large input.

O ranking foi montado considerando 5 pontos por small input correto e 20 pontos por large input correto, o desempate foi feito pelo horário do envio da resposta mais uma penalidade por respostas incorretas na primeira parte.

Meu Desempenho no Qualification Round

Acabei decidindo participar em cima da hora e portanto não fiz nenhuma preparação especial. Optei por usar C pelo fato de ser a linguagem que tenho maior fluência.

Graças ao fuso horário, o horário de competição para mim foi das 20:00 de 16/07 às 20:00 de 17/07. Devido a alguns compromissos pessoais e profissionais, acabei lendo o enunciado da primeira questão às 20:00 mas só trabalhei na resolução dela e da segunda das 21:00 às 24:00. A terceira questão ficou para o dia seguinte, das 18:00 às 20:00 (e não deu tempo, como vou detalhar depois).

Felizmente eu acertei por completo as duas primeiras questões (com uma vacilada na primeira) o que deu pontos suficientes para passar para a próxima fase. Graças ao horário, eu consegui ficar em 1117 dentro dos 6773 que passaram. No total 7154 pessoas fizeram alguma pontuação.

Nos próximos posts vou comentar as três questões e as minhas soluções.