Notebooks

O notebook é basicamente para conter algoritmos relativamente complicados que você entende, mas que os detalhes de implementação podem te trazer problema na hora da prova.

DFS? Dijkstra? Knapsack? Tem que saber de cor! Até decorá-los pode até tê-los como referência, mas evite usar em treinos. E treine eles! Se alguém for competir por uma vaga no Mundial, tem que saber fazê-los sem problema.

O notebook tem que ter ser para algoritmos com detalhes de implementação chatos e passíveis de erros difíceis de encontrar. Encaixam nessa categoria:

• Geométricos, que costumam ter várias implementações possíveis e casos especiais
• Bipartite matching
• Fluxo máximo
• Fluxo de custo mínimo

Nesses problemas que o notebook costuma fazer a diferença de verdade. No Mundial de 2005, por exemplo, havia um problema cujo algoritmo que o resolvia era super simples em alto nível, mas usava fluxo de custo mínimo! O algoritmo é bem complicado de implementar na primeira vez, mas a equipe o ITA tinha no notebook deles e resolveu o problema sem maiores dificuldades e perda de tempo. Outras equipes não tinham o código no notebook. Não porque não sabiam que tinham que tê-lo, mas porque tiveram preguiça de implementá-lo! E com isso não resolveram o problema.

A mensagem é que ter um notebook é importante, mas não basta apenas copiá-los. É essencial entendê-los! Se não você cai em casos tipo: será que essa função funciona para polígonos côncavos? Ou será que estou tomando Wrong Answer por um bug no notebook? E quando isso acontece pode ser 1 hora ou mais de computador desperdiçada. Provavelmente o fim de uma vaga para o Mundial.

Com isso em mente, acho que é muito válido ler o código de competidores experientes para pegar o jeito de escrever códigos concisos e precisos. Para ilustrar esse fato, quando apredi o algoritmo de Dijkstra's, o meu código era horrível. Só começou a ficar bom quando vi como o Guilherme Ottoni, que já tinha bem mais experiência, fazia.

Além dos notebooks abaixo, outra fonte muito boa de códigos de alta qualidade para competições é o arquivo do TopCoder. Dêem uma olhada nas submissões mais bem pontuadas de cada problema. Você vai se surpreender como os caras são espertos e como aquele codigo que você sempre usou pode ser bem mais limpo.