O Qualification Round do Code Jam 2010 ocorreu de sexta às 20:00 até sábado no mesmo horário. Trata-se de uma competição de programação que já mencionei várias vezes aqui no blog. Foram três problemas, cada um com dois conjuntos de teste: um pequeno (que você pode tentar várias vezes e é corrigido na hora) e um grande (que você só pode tentar uma vez e só é corrigido no final). Para passar nesta rodada bastava acertar pelo menos um conjunto pequeno e um grande.
Como é costumeiro nesta competição, os problemas admitiam soluções do tipo "força bruta" adequadas para os conjuntos pequenos, porém insuficientes para os conjuntos grandes.
Com uma gripe e alguns compromissos pessoais, eu optei por dedicar pouco tempo a esta rodada. Na sexta feira eu só dei uma olhada nos problemas. No sábado de manhã eu ataquei o primeiro deles (Snapper Chain) e consegui resolver rapidamente o conjunto pequeno. Um pouco surpreso com a facilidade do problema, processei o conjunto grande e passei a pensar no terceiro problema (Theme Park).
Após alguns rabiscos no papel, encontrei uma solução que me pareceu adequada. Neste ponto fiquei dividido entre implementá-la na hora ou assistir ao treino de Formula 1. Entusiasmado com a minha solução eu resolvi começar a implementá-la. Feita a codificação, testei com os exemplos do enunciado. Corrigido um pequeno erro, apesar do treino já estar começando, parti para o conjunto pequeno que resolvi corretamente. Embalado, processei o conjunto grande, o que demorou alguns segundos. Após enviar o resultado para o concurso, resolvi dar uma olhada no arquivo de saída (o que normalmente eu não faço). Para meu desespero, a saída tinha alguns números negativos, obviamente errados. Um recurso das regras que eu sempre tinha considerado inútil é poder reprocessar o conjunto grande dentro do limite de tempo (8 minutos no caso). Foi o que fiz meio no desespero.
A hipótese mais provável era ter ocorrido um estouro nos cálculos, num erro primário eu não tinha examinado quais os limites possíveis. Fiz uma tentativa trocando int por unsigned, mas não adiantou. Era óbvio que eu precisava usar inteiros de 64 bits, o que requer extensões não padrão no caso do velhusco Visual C v6 que eu estava usando. Corre para achar um exemplo meu do ano passado, alterar o programa, reprocessar (o que demorou vários segundos), conferir que não tinha números negativos e re-enviar. Sobraram ainda 3 minutos e eu fui ver o treino da Formula 1.
Neste ponto eu tinha dois conjuntos pequenos corretos e uma boa esperança de ter acertado pelo menos um dos conjuntos grandes. Sobrava ainda o segundo problema (Fair Warning), mas era claramente o mais difícil deles. Além disso, o enunciado avisava de inteiros de 64 bits eram insuficientes para resolver o conjunto grande. Eu cheguei a pensar em um esboço de solução que talvez fosse suficiente para o conjunto pequeno, mas isto não faria diferença para a classificação. Preferi parar por aí mesmo e só voltei a olhar o site no fim do dia, para o ver o resultado. No final das contas, as minhas soluções estavam corretas e passei com folga para a próxima fase.
Resta contar que eu ganhei um perigoso concorrente: meu filho. Depois que eu comentei sobre o Code Jam no café da manhã ele prontamente se cadastrou e ao final do dia tinha acertado integralmente o primeiro e o terceiro problemas e mais o conjunto pequeno do segundo, garantindo assim uma classificação melhor que a minha.
Nos próximos posts vou comentar as minhas soluções para os dois problemas que eu acertei.
Nenhum comentário:
Postar um comentário