Treino Seleção 2019
O treino do estágio de seleção 2019 será organizado por semanas. Cada semana terá um tópico a estudar e terá 3 componentes obrigatórias: leituras recomendadas, resolução de dois a três problemas e uma aula por vídeo. Para mais informações consultem o regulamento da seleção, que inclui um sumário de cada semana.
Requisitos
Muitos dos problemas que vos serão propostos são provenientes de vários online judges disponíveis (repositórios de problemas e concursos). Como tal é aconselhado que criem uma conta e explorem as seguintes plataformas: CodeForces; Kattis.
Além de problemas originais, o CodeForces incorpora um mini fórum de discussão que contém exposições sobre vários temas técnicos e não técnicos. É principalmente uma plataforma de concursos, por isso podem ainda participar nos vários concursos disponibilizados, quer em tempo real quer virtualmente.
Muitas das leituras que recomendamos são de dois livros:
- Competitive Programmer's Handbook, por Antti Laaksonen, disponível aqui, abreviado como CPH
- Principles of Algorithmic Problem Solving, por Johan Sannemo, disponível aqui, abreviado como PAPS
Devem fazer download de ambos os livros e seguir os capítulos recomendados em cada tópico.
Listagem de semanas
Lista de atalhos
- 1. Semana 15/04 a 21/04: Programação dinâmica
- 2. Semana 22/04 a 28/04: Estruturas de dados
- 3. Semana 29/04 a 05/05: Prova de Treino I
- 4. Semana 06/05 a 12/05: Grafos
- 5. Semana 13/05 a 19/05: Problemas dinâmicos
- 6. Semana 20/05 a 26/05: Prova de Treino II
- 7. Semana 27/05 a 03/06: Output-only (otimização)
1. Semana 15/04 a 21/04: Programação dinâmica
Básicos de Programação dinâmica
Leituras recomendadas:
- Livro CPH, Capítulo 7
Programação dinâmica em DAG
Leituras recomendadas:
- Livro CPH, Capítulo 16.2 (até 'Extending Dijkstra’s algorithm')
Programação dinâmica em dígitos
Leituras recomendadas:
- Livro PAPS, Capítulo 9.5
Problemas do CodeForces
- Ilya and Queries, Ronda #186 (Div. 2), Problema B: Resolver aqui
- Boredom, Ronda #260 (Div. 1), Problema A: Resolver aqui
- Flowers, Ronda #271 (Div. 2), Problema D: Resolver aqui
Aula por vídeo da semana
Data: Dia 20 de Abril às 20:30 (duração de 1 hora)
Tópicos a abordar:
- Programação dinâmica em árvores
- Programação dinâmica com intervalos
Perguntas de consolidação do tema
Depois de ler as leituras obrigatórias desta semana e resolver os problemas devo saber:
- Como identificar subproblemas de um problema e saber discretizá-los de forma a aplicar programação dinâmica.
- Como reconstruir a solução de um problema que calculámos usando programação dinâmica.
- Identificar diferentes tipos de estruturas onde podemos aplicar programação dinâmica (sequências, DAGs, dígitos de um número, árvores, ...)
Programação dinâmica bitmask (EXTRA)
Leituras recomendadas:
- Livro CPH, Capítulo 10
Programação dinâmica e combinatória (EXTRA)
Leituras recomendadas:
- Livro CPH, Capítulo 22
Problemas do CodeForces (EXTRA)
- Journey, Ronda #374 (Div. 2), Problema C: Resolver aqui
- Vasya and Array, Ronda Educational 56, Problema F: Resolver aqui
- Vladik and Memorable Trip, Ronda #416 (Div. 2), Problema C: Resolver aqui
- Helga Hufflepuff's Cup, Manthan Codefest 17, Problema C: Resolver aqui
- Linear Kingdom Races, Ronda #87, Problema E (Difícil): Resolver aqui
- Kalila and Dimna in the Logging Industry, Ronda #189, Problema C (Muito difícil): Resolver aqui
2. Semana 22/04 a 28/04: Estruturas de dados
Implementações da STL: priority_queue, set, map, queue/stack, deque
Leituras recomendadas:
- Livro CPH, Capítulo 4
Segment trees
Leituras recomendadas:
- Livro PAPS, Capítulo 11.2
Problemas do CodeForces
- Remove Extra One, Ronda #450 (Div. 2), Problema C: Resolver aqui
- Pashmak and Parmida's problem, Ronda #261 (Div. 2), Problema D: Resolver aqui
Aula por vídeo da semana
Data: Dia 05 de Maio às 20:30 (duração de 1 hora)
Tópicos a abordar:
- Consolidar segtrees: generalizar funções e queries
- Aplicações em diferentes problemas fundamentais
Perguntas de consolidação do tema
Depois de ler as leituras obrigatórias desta semana e resolver os problemas devo saber:
- Identificar subproblemas comuns em vários problemas que podemos resolver aplicando a estrutura de dados certa: manter uma lista dinâmica e aplicar algumas operações como mínimo ou máximo (BST/set/map); manter uma lista dinâmica de números e saber quantos números há num certo intervalo (set/segment tree); manter uma sequência de números que atualizamos pontualmente e saber informações sobre subintervalos (segment tree).
Outras versões de Segment trees: lazy, 2d (EXTRA)
Leituras recomendadas:
Fenwick trees/BIT (EXTRA)
Leituras recomendadas:
- Livro CPH, Capítulo 9.2
Problemas do CodeForces (EXTRA)
- Segments Removal, Ronda #452 (Div. 2), Problema E: Resolver aqui
- The Bakery, Ronda #426 (Div. 2), Problema D: Resolver aqui
- Lucky Queries, Ronda #104 (Div. 1), Problema E (Difícil): Resolver aqui
- MEX Queries, Ronda Educational 23, Problema F (Difícil): Resolver aqui
3. Semana 29/04 a 05/05: Prova de Treino I
O concurso terá 5 problemas e a duração de 2 horas e meia. Link para o concurso (Prova de Treino I - 2019).
4. Semana 06/05 a 12/05: Grafos
Pesquisas DFS e BFS
Leituras recomendadas:
- Livro CPH, Capítulo 11 (opcional para introdução ao conceito de grafos)
- Livro CPH, Capítulo 12
Algoritmo de Bellman-Ford
Leituras recomendadas:
- Livro PAPS, Capítulo 12.3.2
Algoritmo de Dijkstra
Leituras recomendadas:
- Livro CPH, Capítulo 13, Secção 'Dijkstra's algorithm'
Problemas do CodeForces
- Kefa and Park, Ronda #321 (Div. 2), Problema C: Resolver aqui
- Shortest Path, Ronda #55 (Div. 2), Problema E: Resolver aqui
Aula por vídeo da semana
Data: Dia 19 de Maio às 20:30 (duração de 1 hora)
Tópicos a abordar:
- Grafos direcionados e TopoSort
- Componentes fortemente conexos e Pontes
Minimum spanning trees (EXTRA)
Leituras recomendadas:
- Livro CPH, Capítulo 15 (podem saltar a Secção de DSU se já tiverem visto)
Ciclos de Euler (EXTRA)
Leituras recomendadas:
- Livro CPH, Capítulo 19 até 'Hamiltonian path'
Árvore de pontes (EXTRA)
Leituras recomendadas:
Problemas do CodeForces (EXTRA)
- Edges in MST, Ronda #111 (Div. 2), Problema D: Resolver aqui
- Paths and Trees, Ronda #303 (Div. 2), Problema E: Resolver aqui
- Tanya and Password, Ronda #288 (Div. 2), Problema D: Resolver aqui
- Wizard's Tour, Ronda #434 (Div. 2), Problema F (Difícil): Resolver aqui
- Dirty Arkady's Kitchen, Ronda #423 (Div. 1), Problema F (Difícil): Resolver aqui
5. Semana 13/05 a 19/05: Problemas dinâmicos
Técnicas fundamentais
Leituras recomendadas:
- Livro CPH, Capítulo 9.1 (Introdução a problema dinâmicos)
- Livro CPH, Capítulo 9.4
Decomposição SQRT
Leituras recomendadas:
- Livro CPH, Capítulo 27.1 e 27.2 (tudo até Mo's algorithm)
Problemas do CodeForces
- Periodic RMQ Problem, Ronda Educacional 20, Problema G: Resolver aqui
- Holes, Ronda Beta #13, Problema E: Resolver aqui
Aula por vídeo da semana
Data: Dia 27 de Maio às 20:30 (duração de 1 hora)
Tópicos a abordar:
- Truque de reconstrução de estruturas de dados em O(sqrt(q))
- Exemplos de problemas dinâmicos
Sparse tables e árvores/Lowest common ancestor (EXTRA)
Leituras recomendadas:
- Artigo sobre Sparse Tables
- Livro CPH, Capítulo 18.3
Truque para Segtrees em árvores (EXTRA)
Leituras recomendadas:
Mais exemplos (EXTRA)
Leituras recomendadas:
Problemas do CodeForces (EXTRA)
- Till I Collapse, Ronda #406 (Div. 1), Problema C: Resolver aqui
- Powerful array, Ronda 2 Yandex 2011, Problema D: Resolver aqui
- Misha, Grisha and Underground, Ronda #425 (Div. 2), Problema D: Resolver aqui
- Letters Removing, Ronda #452 (Div. 1), Problema F: Resolver aqui
6. Semana 20/05 a 26/05: Prova de Treino II
O concurso terá 5 problemas e a duração de 3 horas. Link para o concurso (Prova de Treino II - 2019).
7. Semana 27/05 a 03/06: Output-only (otimização)
Introdução a problemas de otimização
Leituras recomendadas:
Algoritmos greedy
Leituras recomendadas:
Problemas do CodeForces
- Little Frog, Ronda Beta #49 (Div. 2), Problema C: Resolver aqui
Aula por vídeo da semana
Data: Dia 2 de Junho às 20:30 (duração de 1 hora)
Tópicos a abordar:
- Estudo de um exemplo: passos para abordar um problema de output-only
Pesquisa local (EXTRA)
Leituras recomendadas:
Problemas do CodeForces (EXTRA)
- Safe cracking, Ronda Beta #41, Problema C: Resolver aqui
- Online Exam, Ronda de Maratona 1 (Difícil/Problema de Maratona): Resolver aqui