Concurso de treino: TBD

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

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

Concurso de treino: TBD

Árvores binárias de pesquisa

Leituras recomendadas:

• Notas de Princeton sobre BSTs

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

Outras versões de Segment trees: lazy, 2d (EXTRA)

Leituras recomendadas:

• Artigo do emaxx sobre Segment trees

Fenwick trees/BIT (EXTRA)

Leituras recomendadas:

• Livro CPH, Capítulo 9.2

Disjoint Set Union (EXTRA)

Leituras recomendadas:

• Artigo do emaxx sobre DSU

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

Concurso de treino: TBD

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

Minimum spanning trees (EXTRA)

Leituras recomendadas:

• Livro CPH, Capítulo 15 (podem saltar a Secção de DSU se já tiverem visto)

Árvore de caminhos mais curtos (EXTRA)

Leituras recomendadas:

• Artigo sobre Shortest-Paths Trees

Ciclos de Euler (EXTRA)

Leituras recomendadas:

• Livro CPH, Capítulo 19 até 'Hamiltonian path'

Árvore de pontes (EXTRA)

Leituras recomendadas:

• Artigo sobre encontrar pontes num grafo
• Artigo sobre a árvore de pontes

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

Concurso de treino: TBD

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)

Estrutura de dados Buckets

Leituras recomendadas:

• Artigo sobre buckets (às vezes também conhecidos como decomposição SQRT, ainda que esta técnica, como indica o artigo anterior, é mais geral), ler secções 'Sqrt-decomposition based data structure' e 'Other problems'

Problemas do CodeForces

• Periodic RMQ Problem, Ronda Educacional 20, Problema G:   Resolver aqui
• Holes, Ronda Beta #13, Problema E:   Resolver aqui

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:

• Exemplo exemplificando usar LCA para resolver problemas dinâmicos em árvores.

Algoritmo de Mo (EXTRA)

Leituras recomendadas:

• Ler secção 'Mo's Algorithm'

Mais exemplos (EXTRA)

Leituras recomendadas:

• Exemplos de aplicações de decomposição SQRT em diferentes estruturas.
• Exemplos de aplicações em problemas.

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

Concurso de treino: TBD

TBD

Leituras recomendadas:

Introdução a problemas de otimização

Leituras recomendadas:

• Artigo sobre problemas de otimização (ler apenas duas primeiras páginas)

Algoritmos greedy

Leituras recomendadas:

• Livro CPH,
• Artigo do Loop sobre algoritmos greedy (um pouco mais formal)

Hill climbing

Leituras recomendadas:

• Artigo sobre Hill Climbing

Problemas do CodeForces

• Little Frog, Ronda Beta #49 (Div. 2), Problema C:   Resolver aqui

Otimização convexa (EXTRA)

Leituras recomendadas:

• Artigo do Loop sobre otimização convexa.

Pesquisa local (EXTRA)

Leituras recomendadas:

• Artigo sobre Simulated Annealing (também conhecido com pesquisa local)

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