Roteiros

De DCC UFMG - Maratona de Programação
Ir para: navegação, pesquisa

Abaixo, estão listados os roteiros de treinamento sugeridos para iniciantes em competições de programação.

Cada roteiro tem um tema e contém material de apoio sobre o assunto tratado, além de 8 ou 9 problemas para serem resolvidos. Os roteiros foram pensados de forma que um iniciante completo inicie seu treinamento já com um bom direcionamento sobre o que estudar, quais temas são importantes e que problemas resolver para se aprender e praticar os principais temas. Após ter terminado o último roteiro, o aluno terá uma boa noção sobre a maioria dos temas cobrados em problemas da Maratona de Programação: Grafos, Programação Dinâmica, Strings, Estruturas de Dados, dentre vários outros.

Os roteiros foram pensados para que os times os sigam no tempo que acharem necessário. Recomendamos que você só avance para o roteiro seguinte depois de ter lido todo o material de apoio e ter feito, no mínimo, 6 dos problemas listados. Alguns roteiros possuem problemas marcados como especialmente importantes. Consideramos imprescindível que todos do time resolvam esses problemas. O ideal, é claro, é que todos os integrantes do time façam todos os problemas.

Juntamente com os links para os problemas, deixamos sempre um segundo link para uma página desta Wiki com uma solução, dicas e observações importantes. Tente ler a solução apenas depois de ter se esforçado o suficiente. Muitas vezes, o processo de chegar em várias soluções erradas ensina mais do que apenas saber a solução correta. Aproveite para aprender o máximo possível com cada problema. Ter ganhado muitos "Accepteds" em juízes online não significa que você aprendeu tudo o que podia com os problemas que resolveu. Mas, às vezes, vale a pena ler uma dica se você considerar que já analisou todas as possibilidades possíveis para atacar o problema e ainda não chegou em uma solução (o que é falso, mas pode parecer verdadeiro).

# Tema
Roteiro 0 Introdução: Problemas simples
Roteiro 1 Ad hoc: Problemas ad hoc (não requerem técnicas especiais) simples
Roteiro 2 Estruturas de dados: STL, pilhas, filas, conjuntos, etc., e busca binária em vetores
Roteiro 3 Paradigmas de resolução de problemas: Divisão e conquista, Backtracking, Força bruta
Roteiro 4 Paradigmas de resolução de problemas: Programação Dinâmica, Algoritmos Gulosos
Roteiro 5 Algoritmos em Grafos: Busca em Profundidade, Busca em Largura, Ordenação Topológica, Grids
Roteiro 6 Algoritmos em Grafos: Caminho mínimo, Árvore Geradora Mínima
Roteiro 7 Miscelânia: Revisão dos tópicos anteriores
Roteiro 8 Strings: String matching, palíndromos
Roteiro 9 Geometria Computacional: Retas, segmentos, interseção
Roteiro 10 Teoria dos Números e Combinatória: Aritmética modular, Equações diofantinas, MMC, MDC, Algoritmo Euclidiano
Roteiro 11 Estruturas de dados: Árvore de Segmentos, Soma de prefixos, Array de diferenças
Roteiro 12 Programação Dinâmica: Uma nova abordagem
Roteiro 13 Teoria dos Grafos: Fluxo Máximo, Corte Mínimo
Roteiro 14 Geometria Computacional: Convex Hull, Polígonos e Círculos
Roteiro 15 Miscelânia: Revisão geral

Roteiros avançados

Depois de ter terminado os roteiros anteriores, você já terá conhecido boa parte dos algoritmos que utilizará em sua carreira de competidor. Mas isto não é tudo! O mais difícil é, na verdade, saber usar, de forma criativa, tudo o que você já aprendeu. Nos próximos roteiros, você encontrará problemas sobre assuntos que você já viu, mas também alguns assuntos novos. Porém, a solução pode não ser tão óbvia, e pedirá criatividade e insights. A dificuldade dos problemas varia, e haverá problemas (mas não todos serão) significativamente mais difíceis do que os dos roteiros anteriores. Bons treinos!

# Tema
Roteiro 17 Problemas variados
Ferramentas pessoais
Espaços nominais

Variantes
Ações
Navegação
Ferramentas