Biblioteca de algoritmos, estruturas de dados e primitivas para maratona de programação do time [UFMG] Rábalabaxúrias (Bruno, Rafael & Papa).
Códigos em C++, em maior parte implementados pelos integrantes do time.
Versão em PDF (provavelmente não atualizada) dos algoritmos pode ser encontrada aqui.
O theoretical (documento com teoremas, identidades e informações teóricas relevantes) pode ser encontrado aqui.
- Convex Hull Trick
- Divide and Conquer DP
- Longest Common Subsequence - O(n+m) de memória
- Mochila - O(n+cap) de memória
- SOS DP
- Segment Tree
- BIT (Fenwick Tree)
- BIT com Soma em Range
- DSU
- DSU Persistente
- Order Statistic Set (GCC)
- SQRT-decomposition
- Sparse Table
- Sparse Table Disjunta
- Wavelet Tree
- MergeSort Tree
- Minqueue - Deque
- Minqueue - Stack
- Range Color
- RMQ <O(n), O(1)>
- RMQ <O(n), O(1)> - Cartesian Tree
- Splaytree
- Splaytree Implicita
- Split-Merge Set
- Split-Merge Set - Lazy
- SQRT Tree
- Treap
- Treap Implícita
- Treap Implícita Persistente
- LCA/HLD
- LCT
- Block-Cut Tree (computa pontes e pontos de articulação)
- Bellman-Ford
- Dominator Tree
- Floyd-Warshall
- Functional Graph
- Blossom
- Centro/Diâmetro em Árvore
- Centroid Decomposition
- Centroid (encontra os centroids da árvore)
- Vertex Cover
- Dijkstra
- Dinic
- AGM Direcionada (arborescência)
- Euler Path / Euler Cycle Linear
- Euler Tour Tree
- Kosaraju
- Kruskal
- Kuhn
- Line Tree
- Max Flow com Lower Bound
- MinCost-MaxFlow
- Prufer Code Linear
- Sack (DSU em árvores)
- Tarjan (SCC) e Compressão de Ciclos (bridge tree)
- Topological Sort
- Isomorfismo de Árvores
- Virtual Tree
- 2-SAT (com recuperação)
- Logaritmo Discreto
- Miller-Rabin
- Inverso Modular
- Teorema Chines do Resto
- FFT
- Fast Walsh Hadamard Transform
- Crivo de Eratosthenes Linear (e variações)
- Detecção de Ciclo - Tortoise and Hare
- Divisão de Polinomios (naive)
- Equação Diofantina Linear
- Exponenciação Rápida
- Eliminação Gaussiana
- Eliminação Gaussiana de XOR
- Karatsuba
- Algoritmo de Euclides
- Algoritmo de Euclides Estendido
- Mulmod O(1)
- Ordem de Elemento do Grupo
- Algoritmo Rho de Pollard (Pollard Rho)
- Distribuição Binomial
- Totiente
- Division Trick
- Simplex
- Big Integer - C++
- Fração
- Números Complexos
- Primitivas Geométricas
- Primitivas Geométricas Inteiras
- Primitivas Geométricas 3D
- Primitivas de Matriz - Exponenciação
- Aritmética Modular
- Primitivas de Polinômios
- Suffix Array O(n)
- Suffix Array O(n log n)
- Suffix Array Dinâmico
- Trie
- Aho-corasick
- Aho-corasick - Autômato
- eertree (Palindromic Tree)
- String Hashing
- String Hashing - módulo 2^61 - 1
- KMP
- Manacher
- Min/max suffix/cyclic shift (lexicográfico) O(n)
- Autômato de Sufixo
- Algoritmo Z
- Area Máxima de Histograma
- Inversion Count
- RMQ Offline com Divide and Conquer
- Área da Uniao de Retangulos
- Arpa's Trick
- Coeficiente Binomial Modular (para valores grandes e mod não tão grande)
- Closest Pair of Points
- Conectividade Dinâmica - DSU
- Conectividade Dinâmica - LCT
- Distinct Range Query - Wavelet
- Distinct Range Query - Persistent Segtree
- Distinct Range Query com Update
- Dominator Points
- Triângulos em Grafos
- Gray Code
- Algoritmo Húngaro (assignment)
- Coloração de Grafo de Intervalo
- Conjunto Independente Máximo com Peso em Grafo de Intervalo
- Longest Increasing Subsequence (recuperando)
- Longest Increasing Subsequence (tamanho)
- Distância Máxima entre Dois Pontos
- Min Fixed Range
- Mininum Enclosing Circle O(n)
- MO
- MO - DSU
- MO em Árvores
- Pontos Dentro de Polígono
- Interseção de Segmentos
- Verificação de Polígono Simples
- Sweep Direction