A preparação das equipes

Competições online

Dentre os sites que disponibilizam contests online, provavelmente os dois mais utilizados são:

Cada um deles tem seu próprio sistema de ranking de usuários e divisões.

  • No CodeForces, os iniciantes no curso podem se sentir mais à vontade na Div 4, enquanto que alunos mais avançados no curso podem ir na Div 3. Naturalmente, com mais experiência nas competições, podem passar para Div 2 e 1.
  • No AtCoder, os iniciantes devem gostar mais do AtCoder Beginner Contest (ABC). Entretanto, talvez consigam resolver somente um ou dois problemas. Alunos mais avançados no curso talvez consigam três a cinco. Os contests Regular Contest (ARC) e Grand Contest (AGC), são melhores para competidores experientes.

Uma vantagem do AtCoder é a regularidade dos contests ABC, quase sempre aos sábados às 9h, com duração de 100 minutos. Já os contests do CodeForces são mais irregulares.

O editorial (orientações de como resolver os problemas) do contest do AtCoder é publicado quase que imediatamente após a conclusão do contest (eventualmente há um atraso em um ou outro problema) e o acesso é bem fácil (há um botão editorial na página principal da competição). Já o editorial do contest do CodeForces fica um pouco mais escondido, em um frame chamado contest materials no canto inferior direito da página do contest.

Ferramentas para treinamento

  • https://vjudge.net/ : o Virtual Judge (VJudge) é um site que permite criar competições online. Não dá para criar questões, mas é possível montar um contest com problemas dos mais diversos sites. Alguns outros pontos interessantes:
    • É possível traduzir problemas e disponibilizar essa tradução também para outros usuários; além disso também é possível colocar um novo nome para o problema;
    • A fonte (site e número do problema) são omitidos durante a competição;
    • Os horários das competições podem ser programados;
    • É possível atribuir pesos para os problemas;
    • Depois do contest, é possível visualizar os códigos (mas os usuários podem bloquear esse acesso no perfil).

Disciplina

Uma sugestão de conteúdo para uma disciplina de preparação é a seguinte:

  • Primeira etapa: a ideia dessa primeira etapa é permitir que os alunos se ambientem e consigam entender a dinâmica da resolução de problemas competitivos. Ao final, pode criar um contest com problemas muito fáceis, apenas para atingir esse objetivo. Alguns pontos para essa primeira etapa:
    • Introdução: visão geral sobre as competições, o que é a maratona de programação, histórico da instituição nas competições, sites de competições
    • C++: o básico para começar a programar (entrada e saída, condicionais, repetições, etc)
    • Estrutura dos problemas: descrição, entrada, saída, exemplos de entrada/saída
    • Resolução: leitura, rascunho de uma solução, implementação, compilação, testes, envio, interpretação das respostas do juiz
  • Segunda etapa: compreendido o básico da resolução de problemas, é hora de aprender as técnicas mais avançadas. Aqui é importante observar o público-alvo e adaptar o leque de conteúdos e suas respectivas profundidades para que fique em um nível adequado. Aqui algumas sugestões de tópicos:
    • STL de C++: vector, algorithms, pair, map, set, multiset e outros
    • Análise assintótica: uma vez que a eficiência pode ser a diferença entre uma solução aceita e uma não aceita por tempo limite excedido, ao menos o básico desse tópico é essencial
    • Combinatória
    • Teoria dos números
    • Backtracking
    • Programação dinâmica
    • Grafos
    • Geometria computacional: esse tópico é mais raro

Livro CSES

O livro Competitive Programmer’s Handbook é uma ótima referência para a disciplina: https://github.com/pllk/cphb/. O site https://cses.fi/problemset/ tem vários problemas cuja solução é discutida no livro.

Base de problemas

  • Atualmente tenho uma planilha com indicação de 228 problemas com as seguintes estatísticas:
    • Fonte: Uva (69), CodeForces Gym (11), CodeForces (27), CSES (23) e AtCoder (98)
    • Categoria: Ad-Hoc (119), Backtracking (15), Guloso (11), Programação dinâmica (28), Grafos (33) e outras
    • Cada problema está classificado dentre 5 níveis de dificuldade: 100 (muito fácil), 200, 300 (médio), 400 e 500 (mais difícil)
  • Caso queira acesso a esse arquivo .csv, entre em contato comigo por email que eu faço o envio