Manual
User Manual:
Open the PDF directly: View PDF .
Page Count: 42
Manual de algoritmos para maratones de programación
Just Code It. Bodhert
16 de noviembre de 2017
4.2.
4.3.
4.4.
4.5.
4.6.
Divisores de un número . . . . . . . . . . . . . .
Máximo común divisor y mı́nimo común múltiplo
Criba de Eratóstenes . . . . . . . . . . . . . . . .
Factorización prima de un número . . . . . . . .
Exponenciación logarı́tmica . . . . . . . . . . . .
4.6.1. Propiedades de la operación módulo . . .
4.6.2. Big mod . . . . . . . . . . . . . . . . . . .
4.7. Combinatoria . . . . . . . . . . . . . . . . . . . .
4.7.1. Coeficientes binomiales . . . . . . . . . .
4.7.2. Propiedades de combinatoria . . . . . . .
Índice
1. Plantillas
2
2. Cosas para tener en cuenta
3
3. Grafos
3.1. BFS . . . . . . . . . . . . . . . . . . .
3.2. DFS . . . . . . . . . . . . . . . . . . .
3.3. Ordenamiento topológico . . . . . . .
3.4. Componentes fuertemente conexas . .
3.4.1. Kosaraju’s algorithm . . . . . .
3.4.2. Tarjan’s algorithm . . . . . . .
3.5. Algoritmo de Dijkstra . . . . . . . . .
3.6. Algoritmo de Bellman-Ford . . . . . .
3.7. Algoritmo de Floyd-Warshall . . . . .
3.7.1. Clausura transitiva . . . . . . .
3.7.2. Minimax . . . . . . . . . . . .
3.7.3. Maximin . . . . . . . . . . . .
3.8. Algoritmo de Prim . . . . . . . . . . .
3.9. Algoritmo de Kruskal . . . . . . . . .
3.9.1. Union-Find . . . . . . . . . . .
3.9.2. Algoritmo de Kruskal . . . . .
3.9.3. Algoritmo de Kruskal CP3 . .
3.10. Algoritmo de máximo flujo . . . . . .
3.11. Teorema de Konig . . . . . . . . . . .
3.11.1. Ejemplo, aplicación Max Flow - Maximum Matching Size . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
. . . . . . . . . . . . . .
Mimimum Vertex Cover
. . . . . . . . . . . . . .
3
. 3
. 4
. 4
. 4
. 5
. 5
. 6
. 7
. 7
. 7
. 8
. 8
. 8
. 8
. 8
. 9
. 9
. 11
. 12
. 12
4. Teorı́a de números
13
4.1. Números romanos . . . . . . . . . . . . . . . . . . . . . . . . . . 13
4.1.1. Árabe a Romano . . . . . . . . . . . . . . . . . . . . . . . 13
4.1.2. Romano a Árabe . . . . . . . . . . . . . . . . . . . . . . . 14
1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
14
14
14
15
15
15
15
15
15
16
5. Programación Dinámica
5.1. Longest increasing subsequence . . . . . . . . . . . .
5.1.1. Orden cuadrático . . . . . . . . . . . . . . . .
5.1.2. Orden logarı́tmico imprimiendo sólo longitud
5.1.3. Orden logarı́tmico imprimiendo la secuencia .
5.2. Problema de la mochila . . . . . . . . . . . . . . . .
5.3. Edit distance . . . . . . . . . . . . . . . . . . . . . .
5.4. Formas de sumar un número . . . . . . . . . . . . .
5.5. Longest Common Substring . . . . . . . . . . . . . .
5.6. Longest Common Subsequence . . . . . . . . . . . .
5.7. Shortest Common Supersequence . . . . . . . . . . .
5.8. Maximum subarray (non-adjacent) sum (1D) . . . .
5.9. Maximum subarray sum (1D) - Kadane’s Algorithm
5.9.1. Maximum circular subarray sum . . . . . . .
5.10. Maximum subrectangle sum (2D) . . . . . . . . . . .
5.10.1. Naı̈ve solution - O(n4 ) . . . . . . . . . . . . .
5.10.2. Using Kadane’s - O(n3 ) . . . . . . . . . . . .
5.11. Maximum subrectangle sum (3D) . . . . . . . . . . .
5.12. Partition problem . . . . . . . . . . . . . . . . . . . .
5.13. Longest Palindromic Substring . . . . . . . . . . . .
5.14. Longest Palindromic Subsequence . . . . . . . . . . .
5.15. Text Justification . . . . . . . . . . . . . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
16
16
16
16
17
18
18
19
19
20
20
20
21
21
21
21
21
22
22
23
25
25
5.16. Burst Balloons . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.17. Wildcard Matching . . . . . . . . . . . . . . . . . . . . . . . . . . 27
5.18. Maximum profit - Best time to buy and sell stock . . . . . . . . . 27
11.Java
41
11.1. File Reader . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
11.2. Base converter . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
6. Geometrı́a
28
6.1. Closest pair of points in a plane . . . . . . . . . . . . . . . . . . . 28
12.Varios
7. Strings
7.1. Algoritmo de KMP . . . . . . . . . . . . . . . . . . . .
7.2. Algoritmo de Booth - Lexicographically minimal string
7.3. sufix /trie/array . . . . . . . . . . . . . . . . . . . . .
7.3.1. suffix trie . . . . . . . . . . . . . . . . . . . . .
7.3.2. suffix array . . . . . . . . . . . . . . . . . . . .
7.3.3. String Matching . . . . . . . . . . . . . . . . .
7.3.4. Longest Common Prefix (LCP) . . . . . . . . .
7.3.5. Longest Repeated Substring) . . . . . . . . . .
7.4. Formatos de impresión . . . . . . . . . . . . . . . . . .
7.4.1. Números . . . . . . . . . . . . . . . . . . . . . .
7.4.2. Strings . . . . . . . . . . . . . . . . . . . . . . .
7.4.3. Formato en Java . . . . . . . . . . . . . . . . .
1.
. . . . .
rotation
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
.
.
.
.
.
.
.
.
.
.
.
.
30
30
30
31
31
31
32
33
34
34
34
34
35
8. Otros
8.1. Binary Search . . . . . . . . . . . . . . . . . . .
8.1.1. Traditional algorithm . . . . . . . . . .
8.1.2. Lower bound . . . . . . . . . . . . . . .
8.1.3. Upper bound . . . . . . . . . . . . . . .
8.2. Binary Search Tree (BST) . . . . . . . . . . . .
8.2.1. Largest BST in a Binary Tree . . . . . .
8.3. Build Binary Tree from PreOrder and InOrder
8.4. Build Binary Tree from PosOrder and InOrder
8.5. BitSet . . . . . . . . . . . . . . . . . . . . . . .
8.6. Máximo orden dado un n . . . . . . . . . . . .
8.7. Suma de grandes números en C++ . . . . . . .
8.8. Largest Rectangle in a Histogram . . . . . . . .
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
35
35
35
36
36
36
36
37
38
38
38
38
39
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
42
Plantillas
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
Source Exif Data:
File Type : PDF
File Type Extension : pdf
MIME Type : application/pdf
PDF Version : 1.5
Linearized : No
Page Count : 42
Page Mode : UseOutlines
Author :
Title :
Subject :
Creator : LaTeX with hyperref package
Producer : pdfTeX-1.40.16
Create Date : 2018:09:11 22:47:11-05:00
Modify Date : 2018:09:11 22:47:11-05:00
Trapped : False
PTEX Fullbanner : This is pdfTeX, Version 3.14159265-2.6-1.40.16 (TeX Live 2015/Debian) kpathsea version 6.2.1
EXIF Metadata provided by EXIF.tools