sexta-feira, setembro 04, 2009

Google Code Jam - Qualification Round 2009

Apesar de tudo que andei escrevendo por aqui, acabei me preparando mal para o Google Code Jam. Os aborrecimentos do começo da semana também não ajudaram muito.

De qualquer forma, na quarta feira estava às 20:00 de frente do micro vendo a contagem regressiva para o início da competição. Nesta fase o tempo não é crítico, já que não existe limite do número de pessoas que passam para a fase seguinte e os problemas ficam disponíveis por 24 horas. O requisito para passar é acertar no mínimo um "small input" e um "large input". Para quem não está a par das regras, são três problemas a serem resolvidos. Para cada problema você pode fazer múltiplas tentativas de resolver um conjunto pequeno de dados ("small input") e apenas uma tentativa de resolver um conjunto grande de dados ("large input"). Nos dois casos existe um limite de tempo entre baixar os dados e enviar a resposta. O resultado do small input é validado na hora, o do large input somente no final do período de prova.

Está nos meus planos comentar cada um dos problemas, mas por hoje vou ficar apenas em uma visão geral. Em uma olhada rápida, o primeiro e o terceiro problemas tinham solução "força bruta" óbvia. O segundo problema me pareceu mais complicado.

Comecei pelo primeiro, implementando uma solução "força bruta" com pequenas otimizações. Quando estava com o programa pronto para tentar o "small input", o site começou a apresentar problema no download. Aproveitei a pausa forçada para fazer testes com volume de dados mais próximo do limite do "large input", o que me mostrou que o meu algorítmo estava muito ruim. Após alguns aperfeiçoamentos, consegui baixar o "small input" e o resultado foi aprovado na primeira. Entusiasmado, baixei o "large" e fiquei torcendo para dar tempo. Não foi instantâneo mas ficou dentro do limite e a partir daí era esperar 24 horas (pois o prazo foi dilatado em função dos problemas no download) para saber se estava certo. Neste ponto já tinham passado mais de duas horas, o que é mau sinal para as próximas etapas onde o tempo total para os três problemas é de 2 a 4 horas.

Ataquei em seguida o terceiro problema, novamente pela força bruta. O programa ficou pronto logo, mas se mostrava bastante lento. Como não exergava uma forma de otimizar, resolvi tentar o "small input" e novamente passei de primeira. No entusiasmo, parti para o "large input" e estourei o tempo.

Com as oportunidades reduzidas, resolvi pensar bastante no segundo problema antes de me arriscar. Fui durmir à meia-noite, com algumas idéias vagas. No começo da manhã seguinte comecei a pensar novamente no problema e finalmente achei uma forma inteligente de atacá-lo. O small input passou de primeira e o large input foi processado num piscar de olhos.

Quinta feira, 3 de setembro, 22:00 - a hora da verdade. E a internet cai (devido à chuva)! Após meia hora de espera, consigo acessar novamente o site. E confirmar que acertei os dois "large input" e estou na próxima fase.

Algumas estatísticas:
  • Os primeiros 2425 marcaram 99 pontos (tudo certo)
  • Dois competidores fizeram 89 pontos (erraram somente um small input e acertaram o large input nos acréscimos)
  • Os competidores nas posições 2428 a 3888 fizeram 76 pontos (erraram um large input). Estou aqui, em 2861.
  • Um competidor fez 69 pontos (acertou somente os large inputs!)
  • Os competidores nas posições 3890 a 4823 fizeram 66 pontos (erraram um small e um large)
  • Os competidores nas posições 4824 a 4828 fizeram 56 pontos
  • Os competidores nas posições 4829 a 5154 fizeram 53 pontos
  • Os competidores nas posições 5155 a 5949 fizeram 43 pontos
  • Os competidores nas posições 5950 a 7835 fizeram 33 pontos
  • Daqui para frente estão os que não passaram: 7836 a 7877 (30 pontos), 7878 a 7898 (23 pontos), 7899 a 8035 (20 pontos) e 8036 a 8605 (10 pontos)

Nenhum comentário: