README.md

Biblioteca

Biblioteca de algoritmos, estruturas de dados e primitivas para Maratona de Programação da UFMG.

Códigos em C++, em maior parte implementados pelos alunos da universidade.

PDF

Versão em PDF dos algoritmos pode ser encontrada aqui.

O theoretical guide (documento com teoremas, identidades e informações teóricas relevantes) pode ser encontrado aqui.

Link para o latex do theoretical: link.

Atualizar o PDF

Detalhes

Para atualizar o PDF primeiro instale o latex executando

sudo apt install texlive-full

O pdf é gerado usando a ferramenta rubber. Para baixá-la execute:

sudo apt install rubber

ou

pip install latex-rubber

Por fim, execute

cd latex
./getlatex.sh

Hash

No PDF, a coluna de hash é o hash de cada linha, exceto se a linha contem um caractere }. Nesse caso, o hash da linha é o hash a partir da linha que fecha o último } da linha atual.

Para ver o hash no vim, seleciona as linhas com Shift+v, e aperta Ctrl+h.

Conteúdo

Programação Dinâmica

• Divide and Conquer DP
• Longest Common Subsequence - O(n+m) de memória
• Mochila - O(n+cap) de memória
• SOS DP
• Subset Sum

Estruturas de Dados

• Segment Tree
  • Segtree Padrão (soma)
  • Segtree 2D (iterativa)
  • Segtreap (equivalente a seg 2D esparsa)
  • Segtree Beats
  • Segtree Colorida (lê os comentários pra saber o que faz)
  • Segtree Esparsa - Lazy
  • Segtree Esparsa - O(q) Memória
  • Segtree Iterativa
  • Segtree Iterativa com Lazy Propagation
  • Segtree de PA
  • Segtree Persistente
  • Segtree Persistente com Lazy
• BIT (Fenwick Tree)
• BIT 2D
• BIT com Soma em Range
• BIT-Sort Tree
• Convex Hull Trick
• Convex Hull Trick Dinâmico
• DSU (e variações)
• Li-Chao Tree
• Li-Chao Tree Lazy
• MergeSort Tree
• Minqueue - Deque
• Minqueue - Stack
• Priority Queue DS
• Order Statistic Set (GCC)
• Range Color
• RMQ <O(n), O(1)>
• Slope Trick
• Sparse Table
• Sparse Table Disjunta
• Splaytree
• Splaytree Implicita
• Split-Merge Set
• Split-Merge Set - Lazy
• SQRT Tree
• Treap
• Treap Implícita
• Treap Implícita Persistente
• Wavelet Tree

Grafos

• LCA/HLD
  • LCA <O(n), O(1)>
  • LCA com Binary Lifting
  • LCA com HLD
  • Heavy-Light Decomposition - Aresta
  • Heavy-Light Decomposition - Vértice
  • Heavy-Light Decomposition sem Update
• LCT
  • Link-cut Tree - Aresta
  • Link-cut Tree - Vertice
  • Link-cut Tree Padrão
• AGM Direcionada (arborescência)
• Articulation Points
• Bellman-Ford
• Block-Cut Tree
• Blossom
• Centro/Diâmetro em Árvore
• Centroid (encontra os centroids da árvore)
• Centroid Decomposition
• Centroid Tree
• Dijkstra
• Dinitz
• Dominator Tree
• Euler Path / Euler Cycle Linear
• Euler Tour Tree
• Floyd-Warshall
• Functional Graph
• Hopcroft Karp
• Isomorfismo de Árvores
• Johnson
• Kosaraju
• Kruskal
• Kuhn
• Line Tree
• Max Flow com Lower Bound
• MinCost-MaxFlow
• Prufer Code Linear
• Sack (DSU em árvores)
• Stable Marriage
• Tarjan (SCC) e Compressão de Ciclos (bridge tree)
• Topological Sort
• Vertex Cover
• Virtual Tree

Matemática

• 2-SAT (com recuperação)
• Algoritmo de Euclides Estendido
• Algoritmo Rho de Pollard (Pollard Rho)
• Avaliação de Interpolação (avalia a interpolação em um x)
• Berlekamp-Massey
• Convolução de GCD / LCM
• Coprime Basis
• Crivo de Eratosthenes Linear (e variações)
• Detecção de Ciclo - Tortoise and Hare
• Distribuição Binomial
• Division Trick
• Eliminação Gaussiana
• Eliminação Gaussiana de XOR
• Equação Diofantina Linear
• Exponenciação Rápida
• Fast Walsh Hadamard Transform
• FFT
• Integral Numérica
• Inverso Modular
• Karatsuba
• Logaritmo Discreto
• Miller-Rabin
• Mulmod O(1)
• Multipoint Evaluation
• NTT
• Operações em Polinômios e Séries de Potências
• Simplex
• Teorema Chines do Resto
• Totiente

Primitivas

• Aritmética Modular
• Big Integer - C++
• Fração
• Matroid
• Primitiva de Calendário
• Primitivas de Matriz - Exponenciação
• Primitivas Geométricas
• Primitivas Geométricas Inteiras
• Primitivas Geométricas 3D

Strings

• Aho-corasick
• Algoritmo Z
• Autômato de Sufixo
• eertree (Palindromic Tree)
• KMP
• Manacher
• Min/max suffix/cyclic shift (lexicográfico) O(n)
• String Hashing
• String Hashing - módulo 2^61 - 1
• Suffix Array O(n)
• Suffix Array O(n log n)
• Suffix Array Dinâmico
• Trie

Problemas

• Algoritmo Húngaro (assignment)
• Área da Uniao de Retangulos
• Area Máxima de Histograma
• Closest Pair of Points
• Coeficiente Binomial Modular (para valores grandes e mod não tão grande)
• Coloração de Grafo de Intervalo
• Conectividade Dinâmica - DSU
• Conectividade Dinâmica - LCT
• Conjunto Independente Máximo com Peso em Grafo de Intervalo
• Convex Hull Dinâmico
• Distância Máxima entre Dois Pontos
• Distinct Range Query com Update
• Distinct Range Query
• Dominator Points
• DP de Dominação 3D
• Fatoração de String em Palíndromos
• Gray Code
• Half-Plane Intersection
• Heap Sort
• Interseção de Ângulos
• Interseção de Segmentos
• Inversion Count
• Longest Increasing Subsequence (recuperando)
• Longest Increasing Subsequence (tamanho)
• Minimum Enclosing Circle O(n)
• Minkowski Sum
• MO
• MO - DSU
• MO em Árvores
• Parsing de Expressão
• RMQ Offline com Divide and Conquer
• Sequência de de Brujin
• Shortest Addition Chain
• Steiner Tree
• Sweep Direction
• Triangulação de Delaunay
• Triângulos em Grafos
• Verificação de Polígono Simples

Extra

• Debug
• fastIO
• Hash
• makefile
• Pragmas
• rand
• Stresstest
• Template C++
• Timer
• vimrc