Primeira Fase: 10 de setembro de 2005
Final Brasileira: 11 e 12 de novembro de 2005
Dicas para Iniciantes
Aqui vão algumas dicas rápidas pra quem não está acostumado com os
tipos de problemas da maratona e de olimpíadas de informática em geral:
Todo problema tem uma entrada exemplo e a saída esperada para aquela
entrada. Você deve sempre se lembrar que essa entrada não é nem de
perto a entrada que os juízes irão usar para testar seu programa. Lembre-se
sempre de que é apenas um exemplo. Após fazer o programa funcionar para
os exemplos, teste sempre condições extremas e de contorno (verifique os
limites do problema, qual os valores mínimo e máximo que as variáveis podem
atingir etc.).
Evite mandar programas precipitadamente. É bem melhor gastar 5 minutos
testando o programa para ter certeza de que funciona para as mais diversas
entradas do que receber uma mensagem de erro dos juízes (que acarreta uma
penalização de 20 minutos).
A maioria dos problemas sempre tem um "truque" escondido. Por exemplo,
suponha um problema trivial de calcular fatorial. Você se lembrou de tratar o
problema quando a entrada é zero? Sempre procure pensar no que o juiz deveria
estar pensando para fazer a entrada. Afinal, o seu programa deve funcionar
corretamente para qualquer entrada...
Se o seu algoritmo lidar com busca, procure cortar ao máximo. Quanto menos
nós expandidos, mais eficiente seu programa. Problemas de busca são, em geral,
críticos com relação ao tempo, e um descuido pode acarretar em estouro do
tempo limite!
A maratona é um torneio de criação e implementação de algoritmos.
Isto significa que você nunca vai precisar se preocupar com coisas do tipo
interface com o usuário, reusabilidade do código etc. Aliás, é bem melhor usar
nomes sugestivos de variáveis do que comentários.
Evite usar as ferramentas de debug, elas consomem muito tempo. Aliás,
deve-se evitar debugar o problema no computador, afinal, são três pessoas para
apenas um computador! Enquanto você estiver debugando o programa na tela do
computador, outros componentes do time podem estar querendo digitar um
programa! O ideal é imprimir o fonte (isso é permitido na maratona) e tentar
analisar o código em busca de erros. Se for indispensável o debug em "tempo
real" procure fazê-lo usando printf de variáveis e técnicas do tipo. Às vezes
breakpoints também podem ser úteis.
Ninguém vai analisar seu código, portanto não interessa se ele está
elegante ou não. Se você tiver uma solução feia, porém eficiente, essa é a que
se deve usar.
Nem sempre um algoritmo polinomial pode ser viável. Suponha que você tenha
implementado um algoritmo O(n^3) para um determinado problema. Mas e se n
puder assumir valores até, digamos, 1000? Com quase toda certeza seu problema
irá estourar o limite de tempo. Por isso, sempre preste atençào não só à
complexidade do seu algoritmo, como à viabilidade de sua implementação.
Não há nada pior do que gastar muito tempo fazendo e implementando um
algoritmo para, depois, descobrir que ele está errado. Numa maratona, esse
erro é fatal. Por isso, apesar de a pressa ser necessária, procure sempre
certifica-se da corretude do algoritmo ANTES de implementá-lo!
Dicas para Iniciantes