Material para Estudo - Semana 02

Olá pessoal,

Nessa semana nós focamos na base das estruturas de dados, ou seja, aprender a usar bem a STL de C++, a qual pode dar um grande impulso no poder de implementação de um competidor, além de termos a base de grafos para resolver problemas (sem nenhum algoritmo específico ainda). Espero que todos realmente estudem o assunto da semana, pois começa a ficar essencial!

Assunto: Estruturas de Dados - Parte 1

Bibliografia principal:

• Competitive Programming, capítulo 2 (2.1, 2.2 e 2.3.1) - Data Structures with Built-in Libraries e Graph
• Introduction to Algorithms, capítulo 10 - Elementary Data Structures
• Top Coder - Power-up C++ with Standard Template Library: Part 1
• Top Coder - Power-up C++ with Standard Template Library: Part 2
• Introduction to Algorithms, capítulo 6 - Heapsort
• Top Coder - Introduction to graphs and their data structures: Section 1

Bibliografia complementar:

• Top Coder - Computational Complexity: Section 1
• Introduction to Algorithms, capítulo 11 - Hash Tables
• Top Coder - Data Structures

Problemas sugeridos:

• UVa 146 (ID Codes): use o next_permutation da STL.
• UVa 514 (Rails): simule a chegada usando uma pilha.
• UVa 1203 (Argus): nem precisa usar a priority_queue, mas é bom para treinar.
• PKU 1002 (487-3279): usar map ou ordenar tudo no final.
• UVa 599 (The Forest for the Trees): somente teoria dos grafos; não precisa de DFS.
• UVa 10720 (Graph Construction): problema bem específico de implementação do Teorema de Erdos-Gallai, mas que pode ser diferencial em competição.