Preparação para concursos de programação

Estamos no início do ano lectivo e isso também significa que a nova temporada de concursos de programação (mais escolares) também está prestes a iniciar-se.

Os alunos do ensino básico e secundário são elegíveis para as Olimpíadas Nacionais de Informática (ONI) e têm a hipótese de serem seleccionados para representar Portugal nas Internacionais, International Olympiad in Informatics (IOI) 2014, em Taiwan. Por seu turno, os alunos universitários poderão competir na Maratona Inter-Universitária de Programação (MIUP) já em Outubro, de modo a qualificarem-se para o South Western European Regional Contest (SWERC), concurso da nossa zona europeia que permite o acesso à final mundial do International Collegiate Programming Contest (ICPC) da ACM.

Independentemente do nível de ensino, a pré-condição fundamental para participar é saber programar. A maioria dos concursos suportam as linguagens C, C++, Java e Pascal. Assim, o primeiro passo é escolher uma delas, estudá-la e praticar para se ser tão proficiente quanto possível.
O C++ é a linguagem mais popular e é a minha linguagem favorita. No entanto, um dos "erros" mais comuns é a falta de conhecimento da Standard Template Library, particularmente os diversos algoritmos já disponíveis na biblioteca algorithm (sort, lower_bound, upper_bound, next_permutation, etc).

Os problemas colocados nestas provas devem ser resolvidos com um programa desenvolvido pelos concorrentes. Para além destes programas serem obrigados a dar as respostas correctas, existem também restrições quanto ao tempo disponível para calcular as respostas e à memória (do computador) disponível.
Assim, os concorrentes devem encontrar as ideias certas para resolver os problemas de forma eficiente, isto é, encontrar o Algoritmo certo para resolver os problemas e implementá-lo usando uma linguagem de programação.

Infelizmente, não conheço muitos recursos em português apropriados para a aprendizagem de algoritmos. As ONI criaram um espaço chamado Academia ONI que contém alguns artigos: "Noções Básicas de Análise de Algoritmos", "Tipos de Problemas" comuns em concursos e "Pesquisa Completa" de soluções. O forum Portugal-a-Programar contém uma secção de Algoritmia e Lógica, da qual recomendo um artigo sobre Grafos.

Dada esta escassez, convém dominar o inglês e explorar tanto os livros como a internet.
A Ciência da Computação é uma área muito vasta. Existem diversos tipos de algoritmos diferentes. Este conhecimento está tipicamente melhor estruturado nos bons livros:

• O meu preferido é o Introduction to Algorithms. Este pode ser considerado uma bíblia e é um pouco difícil de seguir mas é um recurso fenomenal.
• O Programming Challenges é um livro escrito especialmente para concursos e é encontrado facilmente online. 
• Na disciplina de algoritmos na faculdade, era recomendado o Data Structures and Algorithm Analysis in C++, este não é tão completo mas o autor é bastante claro nas suas explicações. 
• Outro livro muito recomendado é o Algorithm Design Manual, mas não o conheço.

Contudo, muitas vezes, quem está a começar nestas coisas não tem ainda vontade de estudar um livro, especialmente os mais jovens (eu também não tinha!). Existem outros tipos de recursos:

• O programa de treino da USACO é uma plataforma de treino para as olimpíadas de informática. Não conheço melhor recurso online para aprender algoritmos e estruturas de dados. Está dividido por módulos que contêm tanto textos de apoio como exercícios para aplicar os conhecimentos transmitidos nesses textos.
• Tutoriais curtos e objectivos. Eu recomendo vivamente os artigos referidos anteriormente em português, assim como os tutoriais do TopCoder.
• Existem cada vez mais cursos online. A disciplina de desenho e análise de algoritmos da Universidade de Stanford é oferecida no Coursera, estando dividida em parte 1 e parte 2.

À medida que os conhecimentos são adquiridos e fortalecidos, é importante exercitar estes conhecimentos. Existem diversos judges online como o Sphere Online Judge. Estes judges disponibilizam um conjunto vasto de problemas e os utilizadores podem resolve-los livremente como treino.
Além dos judges, existem outros sites como o TopCoder, o Codeforces e o CodeChef que organizam competições de treino (normalmente há pelo menos 1 por semana) e é publicado um editorial depois de cada concurso que explica como se poderiam resolver os exercícios.

O post já vai longo, mas já deu certamente para perceber uma coisa: é preciso trabalho, trabalho, trabalho. Tal como em tudo na vida, não existem fórmulas mágicas. No entanto, quem corre por gosto, não cansa :-)