A seletiva para as olimpíadas internacionais usa como referência a Ementa da Olimpíada Internacional de Informática.

Competidores devem utilizar a linguagem C++ e estar familiarizados com todos os conteúdos da ementa da Modalidade Programação, assim como os conteúdos adicionais listados abaixo.

1. Fundamentos de Matemática

Conceitos de Matemática Discreta

• Probabilidade discreta

Conceitos de Grafos

• Grafos planares: fórmula de Euler

2. Fundamentos de Computação

Informática Básica

• Interfaces de linha de comando

Programação

• Bitsets
• Geradores de números aleatórios da biblioteca padrão
• Redirecionamento de entrada/saída para arquivos
• Programação orientada a eventos: algumas tarefas (“interativas” / “comunicativas”) podem envolver interação com um ambiente reativo. O competidor deve ser capaz de:
• Utilizar bibliotecas específicas da competição de acordo com instruções fornecidas durante a prova
• Implementar a interação com o ambiente fornecido

3. Algoritmos e Estruturas de Dados

Estratégias de Algoritmos

• Heurísticas
• Algoritmos randomizados

Estruturas de Dados

• Decomposição avançada:
• Decomposição de estruturas dinâmicas com rebalanceamento
• Algoritmo de Mo
• Árvore de Segmentos 1D Dinâmica
• Estruturas persistentes (por exemplo, Árvore de Segmentos Persistente)
• Árvore de Busca Binária Balanceada (Treap, Splay Tree ou equivalente) 1D
• Técnica de Divisão-e-Conquista para responder consultas em vetor estático
• Union-Find Semi-persistente, Union-Find com Rollback
• Trie de Bits

Algoritmos de Ordenação e Busca

• Quicksort e Quickselect

Algoritmos de Matemática

• Operações simples (adição, subtração e multiplicação) em inteiros de tamanho arbitrário (Big Num)

Algoritmos de Programação Dinâmica

• Programação dinâmica em inteiros de tamanho arbitrário (Digit DP)
• Otimizações avançadas de programação dinâmica:
• Truque do Fecho Convexo (CHT)
• Otimização por Divisão-e-Conquista
• Otimização de Knuth

Algoritmos em Grafos

• 2-SAT (com componentes fortemente conexas)
• Máximo conjunto de arestas independentes em um grafo bipartido (Bipartite Matching) em O(VE)
• Biconectividade em grafos não-direcionados (Bridge Tree, Block-Cut Tree)

Algoritmos em Árvores

• Decomposição em Centroides
• Decomposição Heavy-Light

Algoritmos de Geometria

• Checar se um ponto está em um polígono convexo em O(log N)

---