Google Code Jam 2008 - Online Round 1

Proseguindo no Google Code Jam 2008, tivemos neste fim de semana a primeira rodada para valer. E o meu desempenho foi lastimável, apesar de ter passado para a segunda rodada.

A primeira rodada teve as seguintes diferenças em relação à rodada de qualificação:

• problemas mais difícies
  
• três "baterias", com cada participante podendo participar no máximo de uma
• problemas mais difícies
  
• tempo limitado a duas horas
• problemas mais difícies
• pontuação diferente para as questões
  
• problemas mais ... acho que já deu para pegar a idéia

Quando digo problemas mais difícies, quero dizer que a forma de resolvê-los estava longe de ser óbvia. Além disso, uma solução "força bruta" não tem velocidade suficiente para resolver o "large input".

A primeira bateria que participei foi a 1A, na sexta a noite. E o meu resultado foi o que os tenistas chamam de "pneu" (zero). Eu perdi uns quinze minutos do começo, devido a um problema bobo de login. Dos três problemas, eu cheguei perto de resolver apenas o primeiro (apesar de estar fazendo um complicação desnecessária). Olhando as soluções dos primeiros colocados para os outros dois problemas, não consegui (ainda) entender.

No sábado à tarde tive a segunda e última oportunidade na bateria 1B. Os problemas me pareceram um pouco mais fáceis (ou eu estava com a cabeça mais no lugar). Resolvi atacar primeiro o terceiro problema (que valia mais pontos) pelo método da força bruta. Em pouco mais de trinta minutos eu consegui resolver o "small input", porém chegou perto do limite do tempo (o que significa que não tinha chance para o "large input"). Fiquei algum tempo tentando achar uma forma mais inteligente de resolver o problema, mas não enxerguei. Após gastar mais 30 minutos pensando nos outros dois problemas, resolvi partir para cima do primeiro novamente na base da força bruta. Entretanto, fiz alguma besteira no nervosismo e não consegui passar nem pelo "small input". Olhando as soluções dos primeiros colocados, vi que tinha uma forma bem simples de resolver o primeiro problema. As soluções para os outros dois ainda não entendi.

Graças às pontuações diferentes e o desempate na base do tempo, a minha solução para o terceiro problema (com 15 pontos) me colocou na frente de muita gente que resolveu o primeiro inteiro (5+10 pontos) ou o "small set" do primeiro e do segundo (também 5+10 pontos). Com isto passei para a segunda rodada. Ficou um gosto ruim de ter deixado para trás pessoas que resolveram mais problemas que eu, ainda mais que apelei para a força bruta.

Não acho que faça muito sentido apresentar as minhas soluções. Se tiver disponibilidade de tempo, vou entender as soluções dos primeiros colocados e descrevê-las aqui.

No próximo sábado à tarde tem a segunda rodada, acho pouco provável que eu passe para a terceira.