Ainda Vivo no Code Jam 2010

Bem, pelo menos estou melhor que no ano passado. A primeira rodada do Google Code Jam 2010 ocorreu neste fim de semana e consegui passar para a próxima fase.

As Regras da Rodada

Para esta rodada os participantes tinham até três tentativas. Em cada tentativa os 1000 primeiros passavam para a fase seguinte (e não podiam participar das tentativas seguintes). No fuso horário brasileiro estas tentativas caíram na sexta às 22:00, sábado às 13:00 e domingo às 6:00.

Resumindo as regras, cada tentativa tinha três problemas, com pontuação diferente. Para cada problema você precisa resolver um "small input" e um "large input". O primeiro é corrigido na hora e você pode tentar quantas vezes quiser (e é penalizado pelas tentativas erradas). O segundo é corrigido somente no final e você tem somente uma tentativa. O critério para desempate é o tempo demorado para resolver os problemas.

Primeira Tentativa

A semana passada foi bastante cansativa, tanto no trabalho como na vida pessoal. O resultado foi que na sexta à noite eu olhei os problemas mas não tive ânimo para participar. O meu filho não desperdiçou esta oportunidade e garantiu presença na fase seguinte acertando por completo o primeiro problema e o "small input" do terceiro. O último colocado acertou por completo o primeiro problema em pouco menos de 52 minutos.

Segunda Tentativa

No sábado procurei evitar os erros do ano passado e tratei de almoçar antes da competição. Entretanto, não me saí bem. O primeiro problema me pareceu fácil, o segundo difícil e não vi nem por onde começar o terceiro. Embora o primeiro fosse fácil, eu adotei uma solução trabalhosa, criando vagarosamente uma infra-estrutura que já está pronta na maioria das linguagens. Resultado: demorei uma hora inteira para resolver. E, como a questão era fácil, mais de 1000 concorrentes já tinham resolvido antes. Passei a hora e meia restante pensando como resolver o segundo problema. Terminado o tempo, verifiquei que eu teria que ter resolvido os dois primeiros problemas em menos de 1:26:15 para pegar a última posição. Em outras palavras, eu fiquei insistindo na última hora á toa...

Terceira Tentativa

No domingo eu não estava muito esperançoso e foi difícil levantar da cama neste dia frio e chuvoso. Desta vez decidi atacar os problemas na ordem, em princípio do mais fácil para o mais difícil.

Ao surgir o primeiro problema, um pequeno susto: uma figura sugerindo o envolvimento de geometria. Lendo o problema, entretanto, descobri que envolvia somente a intersecção de retas. Arregacei as mangas e saí rabiscando papel. Em pouco mais de meia hora tinha um programa que resolvia o exemplo no enunciado. Baixei o "small input" - minha resposta foi errada. Um exame rápido no arquivo (felizmente realmente pequeno) e achei o erro. Segunda tentativa - correto. Baixei o "large input" e cruzei os dedos, pois minha solução me parecia mais para força bruta. A execução foi bem rápida, enviei a resposta e parti para o próximo com 40 minutos gastos.

Tive uma certa dificuldade em entender o enunciado do segundo problema. Uma vez entendi, ele me pareceu simples. Implementei, testei com os dados do enunciado, fiz um acerto e tentei o "small input" - correto. Resolvi imediatamente o "large input". Pouco mais de uma hora passada, uma hora e meia e um último problema pela frente.

O enunciado do terceiro problema me pareceu simples e logo vislumbrei uma forma de solução na "força bruta". Resolvi partir para ela mesma. Nos testes com os dados do enunciado achei umas bobagenzinhas, mas a lógica parecia estar funcionando. Hora de tentar o "small input" - CORRETO!. Parti para o "large input" e fiquei esperando o fim do processamento. Após angustiantes 3 minutos o processamento acabou. Dei uma olhada rápida na saída, não vi nada de muito anormal e enviei para o concurso.

Quarenta minutos restando, 41 pontos garantidos e a possibilidade de "gabaritar". Hora de ficar acompanhando o scoreboard. No início os 41 pontos eram suficientes mas com o passar do tempo os concorrentes foram melhorando. Estava claro que eu precisaria acertar pelo menos um dos "large inputs" e/ou torcer para os concorrentes errarem.

Finalmente o resultado: errei somente o "large input" do segundo problema, o que garantiu 78 pontos e a posição 125. O último colocado fez 40 pontos, o que significa que eu teria passado mesmo que tivesse errado os três "large inputs".


Dependendo da correria desta semana publico aqui as minhas soluções. As soluções e comentários oficiais estão aqui.

A cobertura do Google Code Jam no blog está aqui.