Chegámos finalmente ao último artigo deste guia. Começamos por ver os básicos sobre como programar e resolver problemas simples de programação. Vimos o que é um algoritmo e como é que se mede a qualidade de um, usando a noção de complexidade temporal. Vimos os nossos primeiros algoritmos, nomeadamente de ordenação (mergesort) e pesquisa binária. Estudámos o conceito de estruturas de dados e vimos como funciona e como implementar uma pilha. Vimos como funcionam problemas interativos e resolvemos o nosso primeiro. Finalmente vimos alguns conceitos matemáticos que são muito úteis para informática e particularmente para concursos de programação como as Olimpíadas.

Então, vimos tudo o que há para ver? Não! Longe disso... Há ainda imenso para aprenderem sobre algoritmos e estruturas de dados. O objetivo deste artigo é exatamente indicar como continuarem a aprender, no caminho vamos também ver algumas dicas para terem sucesso durante as provas das Olimpíadas.

Próximos passos

Nestes artigos só vimos os conceitos mais básicos. Há imensas estruturas de dados introdutórias que é muito importante conhecer, além das pilhas que vimos, filas, filas de prioridade e árvores binárias de pesquisa. Também irão ver que muitas destas estruturas de dados já se encontram em bibliotecas de C++ e Java, mas para as saberem usar é importante saberem como funcionam. Em termos de algoritmos, irão ver algoritmos greedy, programação dinâmica, algortimos em grafos entre muitos outros. Todos estes conceitos são extremamente importantes para poderem ter sucesso em concursos de algoritmos como as Olimpíadas.

Felizmente existem imensos recursos na internet para poderem aprender tudo isto. Recomendamos o seguinte livro: Principles of Algorithmic Problem Solving, que foi escrito especialmente para iniciantes. O livro ainda está a ser escrito, ou seja, a versão que está disponível online tem algumas falhas, mas vai sendo atualizado. Ainda assim é um excelente recurso. Outro livro muito bom que podem ler é o Competitive Programmer’s Handbook. Este contém alguns temas mais avançados e também é dirigido a leitores um pouco mais experientes.

Uma outra alternativa que têm para treinar é usar a plataforma Loop, que será apresentada na próxima secção. Infelizmente o Loop é um pouco mais incompleto do que os livros acima, especialmente para os mais inexperientes, por isso recomendamos que olhem para os livros (ou um deles) primeiro.

Plataforma Loop

Como já devem ter reparado, este conjunto de artigos insere-se na plataforma Loop. Esta consiste numa coleção de guias, categorizados em diferentes temas, com o objetivo de guiar o vosso treino. Cada guia contém um conjunto de links para artigos ou secções de livros sobre um determinado tema, assim como algumas sugestões de problemas a resolver. Para saberem mais como funciona o Loop o melhor é consultarem o seguinte artigo.

Há duas formas de seguirem o conteúdo: uma é irem olhando para os artigos que se inserem no nível de dificuldade em que se encontram, podem encontrar essa lista aqui. Outra é seguirem a árvore de módulos, que se segue. A árvore de módulos apresenta vários módulos com pré-requisitos, ou seja, é suposto completarem os módulos do topo antes de completarem os mais a baixo. Também é de notar que a árvore de módulos não inclui todos os artigos disponíveis no Loop.

Como treinar

Para treinarem é importante fazer dois tipos de treino: um passivo e um ativo. Por treino passivo entende-se ler conteúdos teóricos, ou seja, ler de um dos livros recomendados, ou um artigo do Loop. Além destes, podem ver soluções de problemas, por exemplo, vários problemas de provas anteriores das Olimpíadas têm uma descrição detalhada da sua solução disponível aqui. Já o treino ativo consiste em resolver problemas sem ver a sua solução ou ainda saber a categoria da solução (por exemplo, os problemas propostos em artigos do Loop normalmente indicam o tema da solução, isto não conta como treino ativo). Para tal é importante resolver concursos de outras provas, por exemplo de Olimpíadas de outros países, ou de outros concursos. Se quiserem uma lista de fontes de problemas deste género, consultem a página de recursos do Loop, que contém ainda mais fontes de material teórico.

Para iniciantes é importante que se foquem primeiro em treino passivo, nomeadamente para aprenderem o máximo de conceitos base possível. Quando já conhecerem todos os temas que mencionámos no início do artigo (algoritmos greedy, programação dinâmica, etc) estão prontos para começarem a fazer algum treino mais ativo. Notamos que a importância do treino ativo está em desenvolver a criatividade necessária para trabalhar um problema. De certo que já olharam para um problema sem ter a mínima ideia de como o resolver (se não, têm de ver mais problemas!), por vezes mesmo conhecendo todas as ferramentas/algoritmos que o problema aborda. Isto é porque para resolver problemas algorítmicos é necessário ter as ideias certas para explorar as propriedades certas e para conseguir fazê-lo é preciso experiência e treino. Dificilmente isto vos vai parecer muito útil no início, mas quando forem um pouco mais veteranos perceberão o porquê.

Dicas para sucesso nas Olimpíadas

Terminamos com algumas dicas para otimizarem a vossa participação nas Olimpíadas. Estas serão dicas gerais que se aplicam a todas as provas (Qualificação, Final e Seleção).

  1. Ler as subtarefas de cada problema: é quase impossível resolver todos os problemas de uma prova das Olimpíadas para 100 pontos (especialmente a Final e Seleção). Os problemas são difíceis e não há muito tempo. MAS, não precisam de o fazer! Cada problema está dividido em subtarefas, já vimos esta divisão nos últimos artigos. Esta divisão é extremamente importante, porque algumas subtarefas são muito mais fáceis que o problema completo, mas mesmo assim podem valer muitos pontos! Quanto abordarem um problema olhem para as subtarefas e estudem as suas restrições. Pensem nas mais simples primeiro de modo a terem ideias para as mais complicadas, mas também para assegurarem alguns pontos. Não se esqueçam que o objetivo das provas é ter o máximo número de pontos, não o máximo número de 100s.
  2. Pensar antes de agir: é muito tentador começar logo a programar uma solução mal acabámos de ler o enunciado de um problema. As Olimpíadas não são uma corrida de velocidade, são uma maratona, por isso não precisam de tentar apressar as coisas. Pensem bem na vossa solução, façam alguns cálculos de qual será a complexidade temporal (ou, no caso de alguns interativos, quantas operações usa o vosso algoritmo). É muito importante olharem para alguns exemplos, não só os fornecidos mas também alguns que vocês criaram à mão, e correrem o vosso algoritmo mentalmente neles, para garantir que funciona. Depois de terem uma boa ideia que funciona, pensem na vossa implementação. Como vão organizar o vosso código? O que vão precisar? Só depois devem começar a teclar. Este tipo de disciplina leva a menos erros e a perderem menos tempo com debug.
  3. Testar o vosso código: esta dica é extremamente importante na qualificação, visto que não têm acesso à vossa pontuação quando submetem o vosso código, mas também é útil nas outras provas se estiverem a ter um "Wrong Answer" que não sabem de onde vem. Testem o vosso código ao gerar alguns casos extra, ou escrevendo-os à mão e calculando a solução à mão ou escrevendo um programa que gera alguns casos aleatórios (para isto convém aprenderem como funcionam as bibliotecas de geração de números aleatórios da vossa linguagem de eleição). Se tiverem algum tempo (como é o caso da Qualificação), é boa ideia escreverem uma solução menos eficiente, mas mais simples e onde por isso é mais difícil cometerem um erro, para a poderem correr em casos de teste que geraram e assim comparar com a vossa solução melhor. Reforçamos que isto é muito importante na qualificação, não querem submeter um código e depois ter um "Wrong Answer" por um erro pequeno porque não testaram.
  4. Gerir o tempo: apesar de terem muito tempo para as provas, ele não é infinito (especialmente durante na Final e na Seleção). Giram bem o vosso tempo! Por exemplo, se tiverem a perder muito tempo a corrigir um programa, mas ainda não têm nenhum ponto nos outros problemas, pode ser boa ideia trocar de problema. Pesem o tempo que gastam em cada coisa pelo número de pontos que ganham. Se precisam de uma hora para corrigir um programa complicado que há tem 60 pontos, para poderem ganhar mais 15, e podem gastar 30 minutos nas subtarefas mais fáceis de outro problema para ganhar 30 ou 40 pontos, façam os 30/40 pontos primeiro!

Claro que cada prova é diferente, quanto mais praticarem mais fácil será de aplicarem estas ideias com sucesso. A teoria é muito diferente da prática como verão! Boa sorte para a vossa participação e lembrem-se que ganhar não é tudo, mas se treinarem e forem aplicados acreditem que é fácil ter sucesso!