CP Algoritmos

Esta obra não está concluída e é uma tentativa de traduzir http://e-maxx.ru/algo e https://cp-algorithms.com para Português. Os artigos são descrições de algoritmos e estruturas de dados especialmente populares no campo da programação competitiva.

---

Artigos

Algebra

• Fundamentos
  • Exponenciação Binária
  • Algoritmo de Euclides (MDC/MMC)
  • Algoritmo de Euclides Estendido
  • Equação Diofantina Linear
  • Números de Fibonacci
• Números Primos
  • Crivo de Eratóstenes
  • Crivo de Eratóstenes com Complexidade Linear
  • Testes de Primalidade
  • Fatoração de Inteiros
• Funções da Teoria dos Números
  • Função totiente de Euler
  • Número de divisores / soma de divisores
• Aritmética Modular
  • Inverso Modular
  • Equação de Congruência Linear
  • Teorema Chinês do Resto
  • Fatorial módulo p
  • Log Discreto
  • Raiz Primitiva
  • Raiz Discreta
  • Multiplicação Modular
• Sistemas Numéricos
  • Ternário balanceado
  • Código de Gray
• Diversos
  • Enumerando submasks de uma bitmask
  • Aritmética Bignum
  • Transformada rápida de Fourier
  • Operações em polinômios e séries

---

Estruturas de Dados

• Fundamentos
  • Mínimo stack/queue
  • Sparse table
• Árvores
  • Árvore Segmentária
  • Disjoint Set Union
  • Árvore de Fenwick / Árvore de Indexação Binária(BIT)
  • Sqrt Decomposition
  • Treap
  • Sqrt Tree
  • Heap aleatório
• Avançado
  • Deletando de uma estrutura de dados em O(T(n)log n)

---

Programação Dinâmica

• DP Otimizações
  • Dividir e Conquistar DP
• Tarefas
  • Problema "Parquet"
  • Maior submatriz de 0's

---

Strings

• Fundamentos
  • String Hashing
  • Rabin-Karp para correspondências de strings
  • Função de Prefixos
  • Função Z
  • Array de Sufixos
  • Algoritmo de Aho-Corasick
• Avançado
  • Árvore de Sufixos
  • Sufixo Autômato
  • Fatoração de Lyndon
• Tarefas
  • Análise de Expressões
  • Algoritmo de Manacher - Encontrando todos os sub-palíndromos em O(N)
  • Encontrando repetições

---

Algebra Linear

• Matrizes
  • Gauss & Sistema de Equações Lineares
  • Gauss & Determinante
  • Kraut & Determinante
  • Ranque de uma matriz

---

Combinatória

• Fundamentos
  • Potência de um divisor fatorial
  • Coeficientes Binomiais
  • Números de Catalan
• Técnica
  • Princípio da inclusão-exclusão
  • Lema de Burnside / Teorema da enumeração de Pólya
  • Estrelas e barras
  • Gerando todas as K combinações
• Tarefas
  • Colocando Bispos em um Tabuleiro de Xadrez
  • Sequência de colchetes balanceados
  • Contando grafos rotulados

---

Métodos Numéricos

• Procura
  • Busca ternária
  • Método de Newton para encontrar raízes
• Integração
  • Integral pela fórmula de Simpson

---

Geometria

• Operações elementares
  • Geometria
  • Encontrando a equação de uma linha para um segmento
  • Ponto de interseção de linhas
  • Checar a interseção de dois segmentos
  • Interseção de segmentos
  • Interseção círculo & linha
  • Interseção círculo & círculo
  • Tangentes comuns a dois círculos
  • Comprimento da união de segmentos
• Polígonos
  • Área orientada de um triângulo
  • Área de um polígono simples
  • Checar se pontos pertencem ao polígono convexo em O(log N)
  • Teorema de Pick
  • Lattice points em um polígono
• Sweep Line
  • Par de segmentos que se cruzam
  • Localização de um ponto em O(log n)
• Convex Hull
  • Construção de um Convex Hull - Scan de Graham
  • Convex Hull e Árvore de Li Chao
• Diversos
  • Encontrando o par de pontos mais próximo
  • Triangulação de Delaunay e diagrama de Voronoi
  • Decomposição Vertical

---

Grafos

• Travessia em grafos
  • Busca em largura - BFS
  • Busca em profundidade - DFS
• Componentes conectados, pontes, pontos de articulação
  • Componentes conectados
  • Encontrando Pontes em O(N+M)
  • Encontrando Pontes Online
  • Localizando pontos de articulação em O(N+M)
  • Componentes fortemente conectados e grafo de condensação
  • Orientação forte
• Caminhos curtos de fonte única
  • Dijkstra - caminho mais curto de um vértice
  • Dijkstra - grafos esparsos
  • Bellman Ford - caminho mais curto com pesos negativos
  • 0-1 BFS
  • D´Esopo-Pape
• Caminhos curtos de todos os pares
  • Floyd Warshall - encontrando todos os caminhos mais curtos
  • Número de caminhos de comprimento fixo / caminhos mais curtos de comprimento fixo
• Árvores geradoras
  • Árvore geradora mínima - algoritmo de Prim
  • Árvore geradora mínima - Kruskal
  • Árvore geradora mínima - Kruskal com Disjoint Set Union
  • Segunda melhor árvore geradora mínima - usando Kruskal e o Menor Ancestral Comum(LCA)
  • Teorema de Kirchhoff
  • Código Prüfer
• Ciclos
  • Checando se um grafo é acíclico e encontrando um ciclo em O(M)
  • Encontrando um ciclo negativo
  • Caminho Euleriano
• Menor ancestral comum (LCA)
  • Menor ancestral comum
  • Menor ancestral comum - Binary Lifting
  • Menor ancestral comum - Farach-Colton e algoritmo de Bender
  • Resolvendo uma RMQ encontrando um menor ancestral comum(LCA)
  • Menor ancestral comum - algoritmo de Tarjan (off-line)
• Fluxos
  • Fluxo máximo - Ford-Fulkerson e Edmonds-Karp
  • Fluxo máximo - Push-relabel
  • Fluxo máximo - Push-relabel otimizado
  • Fluxo máximo - algoritmo de Dinic
  • Fluxo máximo - algoritmo de Malhotra, Pramodh-Kumar e Maheshwari
  • Fluxos com demandas
  • Fluxo de custo-mínimo
  • Solução usando fluxo de custo-mínimo em O (N^5)
• Correspondências
  • Grafo Bipartido
• Diversos
  • Ordenação Topológica
  • Conectividade Aresta / Vértice
  • Coloração de Árvore
  • Satisfatibilidade Booleana
  • Heavy-light decomposition

---

Diversos

• Sequências
  • RMQ (Consulta de Intervalo Mínimo - menor elemento no intervalo)
  • Subsequência crescente mais longa
  • Encontrando a subarray com a máxima/mínima soma
  • K-ésima ordem em O(N)
• Teoria dos jogos
  • Jogos em grafos arbitrários
  • Nim Teorema de Sprague-Grundy
• Cronograma
  • Preparando trabalhos em uma máquina
  • Preparando trabalhos em duas máquinas
  • Preparação otimizada de trabalhos com deadlines e durações
• Diversos
  • Problema de Josephus
  • "15 Puzzle Game": existência de uma solução
  • Árvore Stern-Brocot e sequências de Farey