Google Code Jam 2010: Rodada 2

Neste sábado (5/junho) ocorreu a rodada 2 do Google Code Jam 2010. Estavam classificados para a rodada 3000 competidores; apenas os 500 melhores avançaram para a rodada 3. Eu não estava muito otimista quanto a passar (no que estava correto), ainda mais que nas últimas semanas o rítmo no trabalho tem sido intenso (o que explica também a redução dos posts aqui no blog).

Quando começou a rodada, meu primeiro objetivo era ver se tinha algum problema que eu tivesse uma boa chance de resolver; se não tivesse eu ia simplesmente desistir. Foram 4 problemas, com 2,5 horas para solução. Numa primeira olhada os três primeiros problemas pareciam atacáveis, o quarto envolvia uma geometria pesada. Embora os enunciados fossem razoavelmente simples, nos primeiros 20 minutos ninguém tenha resolvido nenhum problema (nem mesmo um small input). A análise oficial dos problemas pode ser vista aqui.

Eu me interessei pelo problema C (Bacteria), uma versão simplificada do clássico Life. Uma solução "força bruta" capaz de resolver o small input parecia simples. E realmente era, mas levei uma hora para implementar. O problema é que o large input era simplesmente imenso. Tive uma ideia para tentar reduzir a memória necessária e gastei uns 50 minutos implementando uma das minhas soluções complexas, cheia de alocação manual de memória. Para minha surpresa, o código funcionou praticamente de primeira... mas se mostrou muito mais lento que a força bruta! Eu cheguei a imaginar uma terceira solução, mas não tinha certeza se conseguiria implementar nos 40 minutos restantes. Dando uma olhada na classificação, percebi que mesmo que conseguisse resolver o large input não ia dar para passar para a rodada seguinte e entreguei os pontos. Pela análise da Google, esta minha solução não deveria ser suficiente.

A rodada foi realmente difícil. Ninguém conseguiu a pontuação máxima. Somente 12 competidores enviaram uma solução para o large input do último problema, e somente 2 acertaram. Somente os seis primeiros acertaram todo o resto (somente um deles tentou o large input do problema D, mas estourou o tempo). O sétimo colocado acertou os problemas A, B e D, mas não teve tempo para o problema C. O último classificado conseguiu acertar o problema B inteiro e mais o small input do C em uma hora e meia, fazendo 31 pontos (o mesmo que eu teria obtido se tivesse conseguido resolver o problema C inteiro).

Minha principal conclusão da minha participação este ano é que usando C puro não vai dar para ir em frente. Para o ano que vem preciso estar preparado para usar uma linguagem com mais recursos.

Sobra a pendência de apresentar minhas soluções para os problemas que eu resolvi na rodada 1. Vamos ver se as coisas acalmam no trabalho e consigo preparar isto.