segunda-feira, maio 24, 2010

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.

2 comentários:

O peregrino disse...

Fala Daniel,

Muito legal o seu blog! Eu estudo análise de sistema mas ainda estou no 2° semestre e mais pra frente gostaria de participar. Eu gostaria de entender o que é um Small Input e um Large Input? Eu não entendi direito como uma solução pequena e uma grande resolvem o mesmo problema?
[s]
Marcos

Daniel Quadros disse...

Marcos,

Tem uma explicação mais completa lá atrás no blog (aqui), mas segue um resumo.

Normalmente os problemas tem vários casos de teste e cada caso de teste possui parâmetros. No "small input" são poucos casos de teste e os limites para os parâmetros são menores que no "large input".

Por exemplo, considere um problema de ordenação de números. Em cada execução tem N casos de teste e cada caso de teste são fornecidos M números. No "small input" teríamos, por exemplo, um máximo de 10 casos de testes, cada um no máximo 100 números. Praticamente qualquer algorítimo vai resolver isto rapidamente. Já no "large input" teríamos algo como até 1000 casos de testes, cada um com até 10 milhões de número.

Um programa que passe no "small input" pode fracassar no "large input" por estourar o limite de tempo ou por falhar em alguma condição não exercitada no "small input" (o que aconteceu comigo no segundo problema).