Calendário

• Início: 06/06/2022
• Término: 21/09/2022
• Prova final: 21/09/2022
• 08/06/2022: Introdução a C++ e a biblioteca padrão, juízes e complexidade. [Gravação]
• 15/06/2022: Mais estruturas da biblioteca padrão do C++. [Gravação]
• 22/06/2022: Busca completa, permutações e backtracking. Princípios matemáticos de sequências, funções recursivas e inclusão e exclusão.
• 29/06/2022: Soluções gananciosas e programação dinâmica. [Gravação]
• 06/07/2022: Busca binária, divisão e conquista e árvores de Fenwick e de segmentos. [Gravação]
• 13/07/2022: Introdução e busca em grafos e caminho mínimo.
• 20/07/2022: Técnicas diversas: Dois ponteiros, compressão de coordenadas, padrões comuns em maratona. Discussão de problemas anteriores. (semana bônus) [Gravação]
• 27/07/2022: Teoria dos números: Fatoração, crivos, algoritmo de Euclides e Teorema Chinês do Resto. [Gravação]
• 03/08/2022: Árvore geradora mínima, união-busca, componentes conexos e articulações e pontes. [Gravação]
• 10/08/2022: Emparelhamento bipartido, fluxo máximo/corte mínimo e problemas relacionados. [Gravação]
• 17/08/2022: Árvore de segmentos preguiçosa, decomposição em raiz quadrada e algoritmo de mo.
• 24/08/2022: Strings: Trie, KMP, expressões regulares, vetor e autômato de sufixos.
• 31/08/2022: Hashing, jogos combinatórios, Nim e Teorema de Sprague-Grundy.
• 07/09/2022: Decomposição pesado-leve, exponenciação de matrizes e mais. Confira slides anteriores. (semana bônus)
• 14/09/2022: Geometria 2D: Representação de pontos, segmentos e polígonos, varreduras, fecho convexo. (semana bônus)

Programa

Introdução a algoritmos utilizados em programação competitiva.

• Entrada/saída em C++, estruturas de dados e algoritmos da STL
• Busca completa, teste de permutações e backtracking.
• Princípios matemáticos de sequências, funções recursivas e inclusão e exclusão.
• Soluções gananciosas e programação dinâmica.
• Divisão e conquista, busca binária, árvore de Fenwick e de segmentos.
• Busca em grafos, caminho mínimo e menor ancestral comum.
• Dois ponteiros, compressão de coordenadas, padrões comuns em maratona.
• Teoria dos números: Crivo de Eratóstenes, inverso multiplicativo, propriedades do módulo.
• Articulações e pontes, componentes conexos, emparelhamento bipartido e fluxo máximo/corte mínimo.
• Decomposição em raiz quadrada, cadeias (HLD) e algoritmo de Mo.
• Strings: Trie, KMP, expressões regulares, vetor e autômato de sufixos.
• Jogos combinatórios, Nim e Teorema de Sprague-Grundy.
• Geometria: Representação de pontos e polígonos, varredura linear, fecho convexo.
• Outros temas mais avançados dependendo do tempo disponível.

Objetivo

Apresentar problemas de programação competitiva e técnicas para soluções.

• Expor diversos problemas de programação competitiva que exigem diversas técnicas diferentes para resolução.
• Apresentar em detalhe certos algoritmos e estruturas de dados e apontar para referências para aprender mais sobre técnicas específicas.

Avaliação

A cada semana uma nota será atribuída para o desempenho na resolução dos problemas da competição. A nota atribuída é de forma individual e absoluta, não é relativa entre alunos. A média será definida pela soma de todas as notas de todos os exercícios dividas por 12 (15 competições, 3 bônus). Pontos extras (proporcionais a 12) serão atribuídos para problemas resolvidos fora dos prazos de cada competição, valendo metade da nota que seria atribuída caso fossem resolvidos dentro do prazo.

Plano de trabalho

O curso mescla: (1) aulas teóricas expositivas ministradas na forma síncrona, incluindo soluções de problemas; (2) leituras feitas pelos alunos de material disponibilizado pelo professor; (3) a realização de competições de programação semanais com problemas ligados ao tema de semana que serão usadas para avaliação

A disciplina será desenvolvida através de aulas síncronas de 2h de duração. Nestas aulas serão apresentadas as técnicas descritas para resoluções de problemas, e que serão testadas naquela semana.

Os materiais de leitura e a abertura das competições serão disponibilizadas aos alunos logo após a aula síncrona sobre aquele assunto. Espera-se que o aluno gaste 2 horas no decorrer da semana para resolver os exercícios da prova.

A interação efetiva com os alunos irá ocorrer nas aulas síncronas em laboratório e no atendimento remoto via consulta por e-mail. O material das atividades assíncronas será formado de recomendações de leitura, a gravação da aula síncrona e a competição.

Haverá um total de 15 competições semanais, cada uma composta de aproximadamente 5 problemas. A competição terá duração de uma semana a partir da aula semanal. É permitida a discussão geral dos problemas, e a solução contribui para a nota.

Material de leitura e exercícios

• Link temporário com os textos a serem usados.
• Vídeo de Introdução a Maratona para Calouros.

Bibliografia

[1] Antti Laaksonen. Guide to Competitive Programming: Learning and Improving Algorithms Through Contests. Springer International Publishing AG, 2017. DOI : 10.1007/978-3-319-72547-5 .

[2] Steven Halim e Felix Halim. Competitive Programming 3: The New Lower Bound of Programming Contests. 3ª ed. 2013.

[3] Steven S. Skiena. The Algorithm Design Manual. 3ª ed. Texts in Computer Science. Springer International Publishing, 2020. DOI : 10.1007/978-3-030-54256-6.

[4] Thomas H. Cormen et al. Introduction to Algorithms. 3ª ed. The MIT Press, 2009.

[5] C. H. Papadimitriou e K. Steiglitz. Combinatorial Optimization: Algorithms and Complexity. Dover Pub., 1998.

[6] Donald L. Kreher e Douglas R. Stinson. Combinatorial algorithms: generation, enumeration, and search. Discrete Mathematics and Its Applications. Boca Raton, Florida: CRC Press, 1999. ISBN : 9780849339882.

Bibliografia complementar

[7] Antti Laaksonen. Competitive Programmer’s Handbook. 2018. URL: https://cses.fi/book/book.pdf.

[8] Krzysztof Diks et al. Looking for a Challenge 2: Problems from the Polish Collegiate Programming Contest 2011–2014. 2ª ed. University of Warsaw, 2019. URL : https://www.mimuw.edu.pl/~idziaszek/algonotes/looking-for-a-challenge-2-en.pdf.

[9] Jon Kleinberg e Éva Tardos. Algorithm Design. Pearson Education, 2006. URL: https://www.cs.sjtu.edu.cn/~jiangli/teaching/CS222/files/materials/Algorithm%20Design.pdf.

[10] Steven S. Skiena e Miguel A. Revilla. Programming Challenges: The Programming Contest Training Manual. Springler-Verlag New York, 2003. URL: http://acm.cs.buap.mx/downloads/Programming_Challenges.pdf.

[11] Ivanov Maxim et al. CP Algorithms. URL: http://e-maxx.ru/algo/ e https://cp-algorithms.com/ e https://samuraiwesleyjack.github.io/cp-algoritmos/.

[12] Arthur Pratti Dadalto. Ementa Modalidade Programação (OBI). URL: https://olimpiada.ic.unicamp.br/info/ementa/geral/.

[13] Victor de Oliveira Colombo. Material didático sobre algoritmos gulosos. 2018. URL: https://linux.ime.usp.br/~colombo/mac0499/monografia.pdf .

[14] Yan Soares Couto. Algoritmos em sequências. 2016. URL: https://bcc.ime.usp.br/tccs/2016/yancouto/tcc.pdf.

[15] Adrian Vladu e Cosmin Negruşeri. Suffix arrays – a programming contest approach. 2005. URL : http://web.stanford.edu/class/cs97si/suffix-array.pdf.

[16] Maxim Akhmedov. Dynamic programming optimizations. 2017. URL: http://maratona.ic.unicamp.br/MaratonaVerao2017/documents/dp.pdf.

[17] Victor Lecomte. Handbook of geometry for competitive programmers. 2018. URL : https://vlecomte.github.io/cp-geo.pdf.

[18] Pranav A. Sriram. 2014. Olympiad Combinatorics. URL: https://drive.google.com/file/d/1sQtirXxkEfWYuGSKDZ-d7VGYkR_idebY/view.

[19] Cody Johnson. 2015. Algorithms. URL: https://people.bath.ac.uk/masgcs/algorithms.pdf.

[20] C++ Reference. 2021. URL: https://en.cppreference.com.