University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 1 of 14

5 Algoritmos 8
Contents 5.1 Divide and Conqueer D&C . . . . . . . . . 8

University: Universidad Nacional de La Matanza, DIIT

5.1.1 merge_sort.py . . . . . . . . . . . 8
1 Setup 2 5.1.2 Teorema Maestro . . . . . . . . . . 9
1.1 Comando de Ejecución . . . . . . . . . . . 2 5.2 Técnica de 2 Punteros . . . . . . . . . . 9
1.1.1 [Link] . . . . . . . . . . . . . . 2 5.2.1 dos_punteros.py . . . . . . . . . . 9
5.2.2 vectores_paralelos.py . . . . . . . 9
2 Basico 2
2.1 Busqueda Binaria . . . . . . . . . . . . . 2 5.2.3 ventana_deslizante.py . . . . . . . 9
2.1.1 lower_bound.py . . . . . . . . . . 2 5.3 Algoritmo de Mo . . . . . . . . . . . . . 9
2.1.2 upper_bound.py . . . . . . . . . . 2 5.3.1 mo_plantilla.py . . . . . . . . . . 9
2.2 Tabla Aditiva . . . . . . . . . . . . . . 2 5.3.2 mo_ejemplo.py . . . . . . . . . . . 10
2.2.1 tabla_aditiva.py . . . . . . . . . 2
2.2.2 tabla_aditiva_2D.py . . . . . . . . 2 6 Matematicas 10
2.3 Programación Dinámica . . . . . . . . . . 2 6.1 Números Primos . . . . . . . . . . . . . . 10
2.3.1 sub_set_sum.py . . . . . . . . . . 2 6.1.1 criba_eratostenes.py . . . . . . . 10
2.3.2 cambio_monedas.py . . . . . . . . . 2 6.2 Divisores . . . . . . . . . . . . . . . . 10
2.4 Recurrencias Lineales . . . . . . . . . . 2 6.2.1 [Link] . . . . . . . . . . . 10
2.4.1 recurrena_lineal.py . . . . . . . . 2 6.2.2 divisores_un_numero.py . . . . . . 10
2.5 Heap y Heapsort . . . . . . . . . . . . . 3 6.3 Divisor Común Mayor . . . . . . . . . . . 10
2.5.1 [Link] . . . . . . . . . . . . 3
6.3.1 [Link] . . . . . . . . . . . . 10
2.5.2 max_heap.py . . . . . . . . . . . . 3
6.4 Aritmetica Modular . . . . . . . . . . . . 10
3 Grafos 3 6.4.1 aritmetica_modular.py . . . . . . . 10

Team: –ejemplo–
3.1 Leer grafos . . . . . . . . . . . . . . . 3 6.5 Combinatoria . . . . . . . . . . . . . . . 10
3.1.1 [Link] . . . . . . . . . . . . . . 3 6.5.1 [Link] . . . . . . . . . . 10
3.2 BFS: Busqueda en Anchura . . . . . . . . . 3 6.5.2 Precomputo O(N ) . . . . . . . . . . 11
3.2.1 [Link] . . . . . . . . . . . . . . 3 6.6 Elementos de Geometría . . . . . . . . . . 11
3.3 Bipartir un grafo . . . . . . . . . . . . 3 6.6.1 [Link] . . . . . . . . . . . . . 11
3.3.1 [Link] . . . . . . . . . . . . 3 6.6.2 poligono_convexo.py . . . . . . . . 11
3.3.2 bipartir_2.py . . . . . . . . . . . 3 6.7 Capsula Convexa . . . . . . . . . . . . . 11
3.4 Camino Mínimo . . . . . . . . . . . . . . 3
6.7.1 capsula_convexa.py . . . . . . . . 11
3.4.1 [Link] . . . . . . . . . . . . 3
6.8 Teoría de juegos . . . . . . . . . . . . . 12
3.4.2 floyd_warshall.py . . . . . . . . . 4
6.8.1 [Link] . . . . . . . . . . . . . . 12
3.4.3 bellman_ford.py . . . . . . . . . . 4

(UNLaM)
3.4.4 [Link] . . . . . . . . . . . . . . 4 6.9 Identities . . . . . . . . . . . . . . . . 12
3.5 Union Find . . . . . . . . . . . . . . . . 4 6.10 Rodrigues Rotation Formula . . . . . . . . 12
3.5.1 Small To Large . . . . . . . . . . 4 6.11 FFT y NTT . . . . . . . . . . . . . . . . 12
3.5.2 Path Compression y Union by Size . 4 6.11.1 [Link] . . . . . . . . . . . . . . 12
3.6 MST: Árbol Generador Mínimo . . . . . . . 4 6.11.2 [Link] . . . . . . . . . . . . . . 12
3.6.1 [Link] . . . . . . . . . . . . 4
3.6.2 [Link] . . . . . . . . . . . . . . 5 7 Strings 13
3.7 Componentes Fuertemente Conexas . . . . . 5 7.1 Bordes . . . . . . . . . . . . . . . . . . 13
3.7.1 kosaraju_iterativo.py . . . . . . . 5 7.1.1 [Link] . . . . . . . . . . . . . 13
3.7.2 tarjan_iterativo.py . . . . . . . . 5 7.2 Función Z . . . . . . . . . . . . . . . . 13
3.7.3 grafo_condensado.py . . . . . . . . 6 7.2.1 funcion_z.py . . . . . . . . . . . 13
3.7.4 2_SAT.py . . . . . . . . . . . . . 6 7.3 Manacher (Palindromos) . . . . . . . . . . 13
3.8 Components Biconexas, Puentes y Puntos de
7.3.1 [Link] . . . . . . . . . . . . 13
Articulación . . . . . . . . . . . . . . . 6
7.4 Trie . . . . . . . . . . . . . . . . . . . 13
3.8.1 componentes_biconexas.py . . . . . 6
3.9 LCA: Ancestro Común Menor . . . . . . . . 7 7.4.1 [Link] . . . . . . . . . . . . . . 13
3.9.1 binary_lifting_funcional.py . . . . 7
8 Other 14
3.9.2 binary_lifting_lca.py . . . . . . . 7
3.9.3 lca_sparse_table.py . . . . . . . . 7
9 Tablas y Cotas 14
4 Estructuras de Datos 7 9.1 Divisores . . . . . . . . . . . . . . . . 14
Page 1 of 14

4.1 Árbol de Segmentos . . . . . . . . . . . . 7 9.2 Factoriales . . . . . . . . . . . . . . . 14

4.1.1 segment_tree.py . . . . . . . . . . 7
4.1.2 segment_tree_lazy_creation.py . . . 8 10 Consejos 14
4.2 Sparse Table . . . . . . . . . . . . . . . 8 10.1 Debugging . . . . . . . . . . . . . . . . 14
4.2.1 sparse_table.py . . . . . . . . . . 8 10.2 Hitos de prueba . . . . . . . . . . . . . 14
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 2 of 14

Programación Dinámica
Setup 2.3.1 sub_set_sum.py

University: Universidad Nacional de La Matanza, DIIT

Comando de Ejecución
# Solución al Problema Sub Set Sum
1.1.1 [Link] # Problema: Dados:
# * Un conjunto de enteros positivos C = {c1, c2, ..., ck}
# * Un valor V,
cp $[Link] $[Link]; for x in $1*.in; do echo ARCHIVO: $x; cat $x; echo
# Determinar si es posible sumar exactamente V usando elementos de C.
===; python3 $[Link]<$x; echo ===; done | tee -a $[Link]
def sub_set_sum(C, V): #O(n * V)
# Uso: ./[Link] nombre_programa n = len(C)
# Notar que no ponemos nombre_programa.py, sino solo nombre programa A = [False] * (V + 1)
# Importante: Los casos de prueba deben estar en el mismo directorio A[0] = True
que el programa for i in range(n):
# Los archivos de entrada deben tener la extensión .in for j in range(V, C[i] - 1, -1):
# Ej: ./[Link] A para ejecutar el programa [Link] con los casos de A[j] |= A[j - C[i]]
prueba [Link], [Link], etc. return A
#A[i] = True si es posible sumar exactamente i usando elementos de C

Basico 2.3.2 cambio_monedas.py

En esta sección irán los códigos básicos, vistos en la # Solución al problema Cambio de Monedas con DP
categoría Generales del árbol de correlatividades. # Problema: Dados:
# * un conjunto de monedas C = {c1, c2, ..., ck}
Busqueda Binaria # * Un valor V,
# Determinar el mínimo número de monedas de C necesarias para sumar V.
2.1.1 lower_bound.py def cambio_monedas(C, V): #O(n * V)
n = len(C)
# Devuelve el índice del primer elemento mayor o igual a x A = [0] + [float('inf')] * V
# en un arreglo ordenado for i in range(1, V + 1):
def lower_bound(V, x): for j in range(n):
l, r = -1, len(V) if i >= C[j]:
while l < r: # V[l] < x <= V[r] A[i] = min(A[i], A[i - C[j]] + 1)

Team: –ejemplo–
m = (l + r) // 2 return A
if V[m] < x: # A[i] = mínimo número de monedas de C necesarias para sumar i
l = m
else:
r = m Recurrencias Lineales
return r 2.4.1 recurrena_lineal.py
2.1.2 upper_bound.py
# Problema: Dada una recurrencia lineal de la forma
# A[i] = c1 * A[i - 1] + c2 * A[i - 2] + ... + ck * A[i - k]
# Devuelve el índice del primer elemento mayor a x # con A[0], A[1], ..., A[k - 1] dados, determinar A[n] para n >= k.
# en un arreglo ordenado
# ej: Fibonacci(n) = recurrencia([0,1],[1,1],n)
def upper_bound(V, x): # IMPORTANTE: no olvidar el modulo
l, r = -1, len(V)
while l < r: # V[l] <= x < V[r] def recurrencia(A, C, n, mod = int(1e9+7)): # O(n * k)

(UNLaM)
m = (l + r) // 2 k = len(C)
if V[m] <= x: if n < k:
l = m return A[n]
else: A = A + [0] * (n - k + 1)
r = m for i in range(k, n + 1):
return r A[i] = sum(C[j] * A[i - j] for j in range(k)) % mod
return A[n]
Tabla Aditiva # No lo vimos en clase, pero existe una solución más eficiente en
2.2.1 tabla_aditiva.py # O(k^2 * log(n)) usando exponenciación binaria de polinomios.
def recurrencia(A, C, n, mod = int(1e9+7)): # O(k^2 * log(n))
k = len(C)
def crear(V):
if n < k:
n = len(V)
return A[n]
A = [0] * (n + 1)
A = A + [0] * (n - k + 1)
for i in range(n):
def mult(A, B): # Producto de polinomios
A[i + 1] = A[i] + V[i]
n = len(A)
return A #A[i] = sum(V[:i))
C = [0] * n
def consulta(A, l, r): for i in range(n):
return A[r] - A[l] #sum(V[l:r)) for j in range(n):
C[i] += A[j] * B[i - j]
2.2.2 tabla_aditiva_2D.py C[i] %= mod
return C
def exp(A, n): # Potencia rápida de polinomios
# Permite crear y consultar una tabla aditiva para matrices 2D en O(n if n == 1:
* m) y O(1) respectivamente. return A
def crear(M): #M: matriz, O(n * m) if n % 2 == 0:
n, m = len(M), len(M[0]) return exp(mult(A, A), n // 2)
A = [[0] * (m + 1) for _ in range(n + 1)] return mult(A, exp(A, n - 1))
for i in range(n): C = [0] * (k * k)
Page 2 of 14

for j in range(m): for i in range(k):

A[i + 1][j + 1] = A[i + 1][j] + A[i][j + 1] - A[i][j] + M[ C[i * k + i] = 1
i][j] C = exp(C, n - k)
return A #A[i][j] = sum(M[:i)[:j)) for i in range(k):
A[n] += C[i] * A[k - i]
def consulta(A, l1, r1, l2, r2): #O(1) A[n] %= mod
return A[r1][r2] - A[l1][r2] - A[r1][l2] + A[l1][l2] #sum(M[l1:r1) return A[n]
[:l2:r2))
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 3 of 14

Heap y Heapsort bolsa, it = [inicio], 0

while it < len(bolsa):
2.5.1 [Link]

University: Universidad Nacional de La Matanza, DIIT

nodo = bolsa[it]
for vecino in ady[nodo]:
# heap: Estructura de datos que permite mantener un conjunto de if dist[vecino]>dist[nodo]+1:
# elementos ordenados y permite insertar y extraer el mínimo dist[vecino] = dist[nodo]+1
# en O(log n) [Link](vecino)
# heappush(h, x): Inserta x en el heap h it = it+1
# heappop(h): Extrae el mínimo del heap h return dist
# h[0] es el mínimo del heap h
# heapsort: Ordena un iterable en O(n log n) Bipartir un grafo
from heapq import heappush, heappop 3.3.1 [Link]
def heapsort(iterable):
h = []
for value in iterable: # Decide si un grafo puede ser bipartito
heappush(h, value) # Es decir, asignar a cada nodo uno de dos colores
return [heappop(h) for i in range(len(h))] # de tal forma que no haya dos nodos vecinos del mismo color
# Si se puede, retorna True y la lista de colores
2.5.2 max_heap.py # Si no, retorna False y una lista vacía
def Bipartir(ady:list[list[int]])->tuple[bool,list[int]]:
from heapq import heappush, heappop N = len(ady)
def push_inv(h, x): color = [-1]*N
heappush(h, -x) for inicio in range(0,N):
if color[inicio] != -1: continue
def pop_inv(h): color[inicio] = 0
return -heappop(h) bolsa, it = [inicio], 0
while it < len(bolsa):
def get_inv(h):
nodo = bolsa[it]
return -h[0]
for vecino in ady[nodo]:
if color[vecino]==-1:
color[vecino] = 1-color[nodo]
Grafos [Link](vecino)
elif color[vecino]==color[nodo]:

Team: –ejemplo–
return (False,[])
Leer grafos it = it+1
3.1.1 [Link] return (True,color)

3.3.2 bipartir_2.py
# Notar que el codigo no cambia si el grafo es ponderado o no
def leer_lista_aristas(m):
return [ # Dado un grafo con aristas con etiquetas 0 y 1
list(map(lambda x : int(x)-1, input().split())) # * Las etiquetas 0 indican que ambos nodos deben tener el mismo color
for _ in range(m) # * Las etiquetas 1 indican que ambos nodos deben tener colores
] distintos
# Decide si es posible colorear el grafo con dos colores
# ady[u] son los nodos a los que llegan aristas desde u # de tal forma que se cumplan todas las etiquetas
def leer_lista_adyacencia(n,m): # Si se puede, retorna True y la lista de colores
# reutilizo código # Si no, retorna False y una lista vacía
aristas = leer_lista_aristas(m)

(UNLaM)
def Bipartir2(ady: list[tuple[int,int]]) -> tuple[bool, list[int]] :
ady = [[] for _ in range(n)]
for arista in aristas: # arista es (vecino, peso)
u = arista[0] N = len(ady)
v = arista[1] color = [-1]*N
for inicio in range(0,N):
# Para grafo ponderado if color[inicio] != -1: continue
ady[u].append([v]+arista[1:]) color[inicio] = 0
ady[v].append([v]+arista[1:]) # no dirigido bolsa, it = [inicio], 0
# Para grafo no ponderado while it < len(bolsa):
ady[u].append(v) nodo = bolsa[it]
for vecino, peso in ady[nodo]:
ady[v].append(u) # no dirigido
if color[vecino]==-1:
return ady color[vecino] = peso ^ color[nodo]
[Link](vecino)
# inc[u] son las aristas incidentes al nodo u elif color[vecino] == color[nodo] ^ peso:
def leer_lista_incidencia(n,m): return (False, [])
aristas = leer_lista_aristas(m)
inc = [[] for _ in range(n)] it = it+1
for i,arista in enumerate(aristas): return (True,color)
u = arista[0]
v = arista[1] Camino Mínimo
inc[u].append(i)
inc[v].append(i) # no dirigido
3.4.1 [Link]
return inc, aristas
import heapq
BFS: Busqueda en Anchura # Implementación O(M * log N) de Dijkstra con heap
3.2.1 [Link] # Es en casi todo caso lo recomendable
# Recibe un nodo de origen y una lista de adyacencia
# Devuelve la distancia mínima de origen a cada nodo
Page 3 of 14

# Recorrido de BFS de un grafo # float('inf') si no es alcanzable

# Recibe la lista de adyacencia y un nodo de origen # Funciona tanto para ponderado como para no ponderado
# Devuelve la distancia del origen a cada nodo # Recordar que Dijkstra no soporta pesos negativos
# inf para nodos inalcanzables
def BFS(inicio : int, ady:list[list[int]])->list[int]: def DijkstraHeap(origen : int, G : list[list[tuple[int,int]]]):
N = len(ady) distancias = [float('inf')] * len(G)
dist = [float('inf')]*N distancias[origen] = 0
dist[inicio] = 0 procesados = [False] * len(G)
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 4 of 14

for u in range(len(G)):
heap = [] for v, w in G[u]:

University: Universidad Nacional de La Matanza, DIIT

[Link](heap, (0, origen)) distancias[v] = min(distancias[v], distancias[u] + w)
while heap: return distancias
dist, nodo = [Link](heap)
if procesados[nodo]: 3.4.4 [Link]
continue
procesados[nodo] = True # Modificación de BellmanFord
for (vecino, distancia) in G[nodo]: # Calcula la distancia desde el origen a todos los demás nodos
if distancias[vecino] > distancias[nodo] + distancia: # Soporta pesos negativos
distancias[vecino] = distancias[nodo] + distancia # En el caso promedio: O(N + M)
[Link](heap, (distancias[vecino], vecino)) # En el peor caso: O(N * M)
return distancias def SPFA(origen : int, G : list[list[tuple[int,int]]]) -> list[int]:
# Implementación O(N^2) de Dijkstra distancias = [float('inf')] * len(G)
# Solo recomendable en grafos densos donde M ~ N^2 distancias[origen] = 0
# Recibe y devuelve o mismo que la implementación anterior. cola = [origen]
def DijkstraCuadratico(origen : int, G : list[list[tuple[int,int]]]): i = 0
distancias = [float('inf')] * len(G) en_cola = [False] * len(G)
distancias[origen] = 0 while i < len(cola):
procesados = [False] * len(G) u = cola[i]
en_cola[u] = False
for _ in range(len(G)):
for v, w in G[u]:
siguiente = -1
if distancias[v] > distancias[u] + w:
for i in range(len(G)):
distancias[v] = distancias[u] + w
if not procesados[i] and (siguiente == -1 or distancias[i] <
if not en_cola[v]:
distancias[siguiente]): [Link](v)
siguiente = i
en_cola[v] = True
if siguiente == -1:
i += 1
break return distancias
procesados[siguiente] = True
for (vecino, distancia) in G[siguiente]: Union Find
if not procesados[vecino] and distancias[vecino] > distancias[
siguiente] + distancia: 3.5.1 Small To Large

Team: –ejemplo–
distancias[vecino] = distancias[siguiente] + distancia
# Implementa union find utilizando la técnica de
return distancias
# small to large
# Notar que n se debe definir antes en el código
3.4.2 floyd_warshall.py
id = [i for i in range(n)]
# Inicialmente cada nodo esta en su propia componente
# Calcula la distancia mínima de cada nodo a cada nodo
# Soporta pesos negativos cmp = [[i] for i in range(n)]
# Retorna una matriz de distancias # Retorna True si se unieron los nodos,
# O(N^3) # False si ya estaban en la misma componente
def FloydWarshall(G : list[list[tuple[int,int]]]): def union(u, v):
distancias = [[float('inf')] * len(G) for _ in range(len(G))] u, v = id[u], id[v]
for u in range(len(G)): if u == v: return False # No se los unio
distancias[u][u] = 0 if len(cmp[u]) < len(cmp[v]): u, v = v, u
for v, w in G[u]: for x in cmp[v]:

(UNLaM)
distancias[u][v] = w cmp[u].append(x)
for k in range(len(G)): id[x] = u
return True
for i in range(len(G)):
for j in range(len(G)): 3.5.2 Path Compression y Union by Size
distancias[i][j] = min(distancias[i][j], distancias[i][k] +
distancias[k][j]) # Implementa union find con las optimizaciones
return distancias # de path compression y union by size comentadas
# en la clase
3.4.3 bellman_ford.py # Notar que n se debe definir antes en el código
pad = [i for i in range(n)]
# Recibe un nodo de origen, una lista de adyacencia y una longitud L # Inicialmente cada nodo es su propio padre
# Calcula para cada nodo y longitud la distancia mínima del origen a sz = [1] * n
# ese nodo con exactamente esa cantidad de aristas. # tamaño de las componentes
# Soporta pesos negativos.
def find(u):
# O((N+M) * L) tiempo, O(N*L) memoria
visto = []
def BellmanFord(origen : int, G : list[list[tuple[int,int]]], L : int) while u != pad[u]:
-> list[list[int]]: [Link](u)
distancias = [ [float('inf')] * len(G) for _ in range(L+1) ] u = pad[u]
distancias[0][origen] = 0 for x in visto:
for l in range(L): pad[x] = u
for u in range(len(G)): return u
for v, w in G[u]: # Retorna True si se unieron los nodos,
distancias[l+1][v] = min(distancias[l+1][v], distancias[l][u] # False si ya estaban en la misma componente
+ w) def union(u, v):
return distancias u, v = find(u), find(v)
if u == v: return False
# Similar a la anterior pero retorna para cada nodo
if sz[u] < sz[v]: u, v = v, u
Page 4 of 14

# la minima distancia del origen.

# Garantiza que probo al menos todos los caminos de L aristas o menos. pad[v] = u
# O((N+M) * L) tiempo pero O(N) memoria sz[u] += sz[v]
return True
def BellmanFordLigero(origen : int, G : list[list[tuple[int,int]]], L
: int) -> list[int]:
distancias = [float('inf')] * len(G)
MST: Árbol Generador Mínimo
distancias[origen] = 0 3.6.1 [Link]
for l in range(L):
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 5 of 14

# Dada una lista de aristas, calcula el MST [Link](v)

# MST: Árbol Generador Mínimo break

University: Universidad Nacional de La Matanza, DIIT

# Notar que es necesario implementar también un union find if arista[u] == len(g[u]):
# O(M log M) [Link](u)
# Devuelve el costo y la lista de aristas del MST
for u in range(n):
def Kruskal(g : list[tuple[int,int,int]]):
if not visitados[u]:
# -> tuple[int, list[tuple[int,int,int]]]: dfs(u)
[Link](key=lambda x: x[2])
global n, id, cmp # Transpongo el grafo
n = max([a[0] for a in g] + [a[1] for a in g]) + 1 gt = [[] for _ in range(n)]
id = [i for i in range(n)] for u in range(n):
cmp = [[i] for i in range(n)] for v in g[u]:
cost = 0 gt[v].append(u)
mst = []
for a in g: # En el transpuesto recorro según el orden inverso de salida de
DFS
if union(a[0], a[1]):
# usemos el union-find que nos guste cmp = [-1] * n
cmp_id = 0
cost += a[2]
[Link](a) def marcar_componente(u : int):
return cost, mst pila = [u]
while pila:
3.6.2 [Link] u = [Link]()
if cmp[u] != -1: continue
cmp[u] = cmp_id
import heapq
# Dada una lista de aristas, calcula el MST for v in gt[u]:
if cmp[v] == -1:
# MST: Árbol Generador Mínimo
[Link](v)
# O(M log M)
# Devuelve el costo y la lista de aristas del MST # Recorro el grafo
for u in reversed(ord):
def Prim(g : list[tuple[int,int,int]], start : int = 0) :
if cmp[u] == -1:
# -> tuple[int, list[tuple[int,int,int]]]:
marcar_componente(u)
heap = [(0,-1,start)] cmp_id += 1

Team: –ejemplo–
costo = 0
mst = [] return cmp
n = max([a[0] for a in g] + [a[1] for a in g]) + 1
adj = [[] for _ in range(n)] 3.7.2 tarjan_iterativo.py
for a in g:
adj[a[0]].append((a[1],a[2])) def Tarjan(g : list[list[int]]) -> list[int] :
adj[a[1]].append((a[0],a[2])) n = len(g)
used = [False] * n cmp = [-1] * n
while heap: cmp_id = 0
w,u,v = [Link](heap) tiempo = 0
if used[v]: continue
used[v] = True entrada = [-1] * n
if u != -1: min_entrada = [-1] * n
costo += w arista = [0]*n
[Link]((u,v,w))
def dfs(u):

(UNLaM)
for x in adj[v]: nonlocal cmp_id
if not used[x[0]]: nonlocal tiempo
[Link](heap,(x[1],v,x[0]))
return costo, mst pila = [u]
pila_cmp = []
Componentes Fuertemente Conexas while pila:
u = pila[-1]
3.7.1 kosaraju_iterativo.py [Link]()
if entrada[u] == -1:
entrada[u] = tiempo
# Recibe la lista de adyacencia de un grafo dirigido
min_entrada[u] = tiempo
# Devuelve una lista con el id de la componente
tiempo += 1
# fuertemente conexa a la que pertenece cada nodo
pila_cmp.append(u)
# O(N+M) tiempo
while arista[u] < len(g[u]):
def Kosaraju(g : list[list[int]]) -> list[int] :
v = g[u][arista[u]]
n = len(g)
if entrada[v] == -1:
ord = []
[Link](u)
# Ordeno usando simil BFS [Link](v)
d_in = [0] * n break
for u in range(n): elif entrada[v] > entrada[u]:
for v in g[u]: min_entrada[u] = min(min_entrada[u], min_entrada[v
d_in[v] += 1 ])
elif cmp[v] == -1:
visitados = [False] * n
min_entrada[u] = min(min_entrada[u], entrada[v])
arista = [0] * n
arista[u] += 1
# Hago un pseudo-toposort con DFS iterativo if arista[u] == len(g[u]) and entrada[u] == min_entrada[u
def dfs(ini): ]:
pila = [ini] while True:
while pila: v = pila_cmp.pop()
Page 5 of 14

u = [Link]() cmp[v] = cmp_id

visitados[u] = True if v == u: break
cmp_id += 1
while arista[u] < len(g[u]):
v = g[u][arista[u]] for u in range(n):
arista[u] += 1 if cmp[u] == -1:
if not visitados[v]: dfs(u)
[Link](u) return cmp
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 6 of 14

3.7.3 grafo_condensado.py res[x] = u<n

return res

University: Universidad Nacional de La Matanza, DIIT

# Dado un grafo dirigido g, retorna el grafo condensado
# de g y la componente fuertemente conexa de cada nodo Components Biconexas, Puentes y Puntos de
# Recordar: El grafo condensado de G es aquel en el que
# cada componente fuertemente conexa de G es un nodo Articulación
# y hay una arista de un nodo U a otro V si en G hay 3.8.1 componentes_biconexas.py
# una arista de un nodo u en U a un nodo v en V
# Requiere Tarjan o Kosaraju ya implementado
# O(N+M) tiempo # Indentifica los puentes, puntos de articulación y componentes
# biconexas de un grafo no dirigido, recibiendo la lista de incidencia
def Condensado(g : list[list[int]]) -> list[list[int]]: # g y la lista de aristas ars (cada arista es una tupla de dos nodos)
cmp = Tarjan(g) # Puede ser Kosaraju # Puente: Arista que si elimina aumentan lac antidad de componentes
n_cmp = max(cmp)+1 # conexas del grafo
gc = [[] for _ in range(n_cmp)] # Punto de articulación: Nodo que si se elimina aumenta la cantidad
for u in range(len(g)): # de componentes conexas del grafo
for v in g[u]: # Componente biconexa: Subgrafo conexo que no tiene puntos de
if cmp[u] != cmp[v]: # articulación.
gc[cmp[u]].append(cmp[v]) # Notar que la división en componentes biconexas es una partición
for u in range(n_cmp): # de las aristas del grafo (cada arista pertenece a una unica
gc[u] = list(set(gc[u])) # componente biconexa) pero no de los nodos, los puntos de
return (gc, cmp) # articulación pertenecen a más de una componente biconexa
# O(N+M) tiempo
3.7.4 2_SAT.py def Biconexas(g : list[list[int]], ars : list[tuple[int,int]]):
# -> tuple[list[int], list[bool], list[bool]] :
# Problema de 2-Satisfactibilidad # Primero: Componente biconexa de cada arista
# Segundo: Para cada nodo, si es punto de articulación
# Dada una fórmula en forma normal conjuntiva (CNF) # Tercero: Para cada arista, si es puente
# con 2 variables por cláusula, n = len(g)
# determinar si existe una asignación de valores a m = len(ars)
# las variables que haga verdadera
# a la fórmula. cmp = [-1] * m
# La fórmula se representa como una lista de cláusulas, punto = [0] * n
puente = [0] * m

Team: –ejemplo–
# donde cada cláusula es una
# tupla de dos elementos. Si el primer elemento de la padre = [-1] * n
# tupla es positivo, se afirma la variable correspondiente.
# Si el segundo elemento de la tupla es positivo, se llegada = [-1] * n
# afirma la variable correspondiente. Si el primer elemento min_alcanza = [-1] * n
# de la tupla es negativo, se niega la variable correspondiente. tiempo = 0
# Si el segundo elemento de la tupla es negativo, se niega la pila = []
# variable correspondiente. indice = [0] * n
componente = 0
# La función retorna una lista de booleanos, donde el i-ésimo
# booleano indica si la variable i debe ser verdadera o falsa. def DFS(u):
# Si no existe una asignación que haga verdadera a la fórmula, nonlocal tiempo, componente
# retorna una lista vacía. pila_dfs = [u]
# La función tiene complejidad O(N+M), donde while len(pila_dfs) > 0:
# N es el número de variables y u = pila_dfs.pop()
# M es el número de cláusulas.

(UNLaM)
# Ejemplo de uso: if llegada[u] == -1:
# f = [(1,2),(-1,-2),(1,-2),(-1,2)] llegada[u] = tiempo
# print(SAT2(2,f)) # [True, True] min_alcanza[u] = tiempo
# print(SAT2(2,[(1,2),(1,-2),(-1,2),(-1,-2)])) # [] tiempo += 1
# Necesita tener implementado Condensado y Toposort ar = g[u][indice[u]]
def SAT2(n : int, f : list[tuple[int,int]]) -> list[bool]: v = ars[ar][0] + ars[ar][1] - u
# Formato input: >0 afirmo variable, <0 niego variable if ar != padre[u]:
g = [[] for _ in range(2*n)] if llegada[v] == -1:
def neg(x): padre[v] = ar
return x+n if x<n else x-n pila_dfs.append(u)
pila_dfs.append(v)
# Construyo el grafo de implicancias que modela el problema
[Link](ar)
for (p1, p2) in f: continue
x1 = p1 - 1 if p1>0 else neg(-p1-1)
x2 = p2 - 1 if p2>0 else neg(-p2-1) if padre[v] == ar:
g[neg(x1)].append(x2) if min_alcanza[v] > llegada[u]: puente[ar] = True
g[neg(x2)].append(x1) if min_alcanza[v] >= llegada[u]:
punto[u] += 1
# Calculo el grafo condensado last = [Link]()
(gc, cmp) = Condensado(g) while last != ar:
componentes = [[] for _ in range(len(gc))] cmp[last] = componente
for u in range(2*n): last = [Link]()
componentes[cmp[u]].append(u) cmp[ar] = componente
componente += 1
# Reviso que no haya contradicción
min_alcanza[u] = min(min_alcanza[u], min_alcanza[v])
for i in range(n):
elif llegada[v] < llegada[u]:
if cmp[i]==cmp[i+n]:
[Link](ar)
return []
min_alcanza[u] = min(min_alcanza[u], llegada[v])
# Asigno valores a las variables
Page 6 of 14

res = [-1] * n indice[u] += 1

if indice[u] < len(g[u]):
orden = Toposort(gc) pila_dfs.append(u)
continue
for U in reversed(orden):
for u in componentes[U]: for i in range(n):
x = u if u<n else neg(u) if padre[i] == -1:
if res[x]==-1: punto[i] -= 1
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 7 of 14

DFS(i) [Link][i - 1][[Link][i - 1][v]]

punto = [punto[i] > 0 for i in range(n)]
3.9.3 lca_sparse_table.py

University: Universidad Nacional de La Matanza, DIIT

return cmp, punto, puente

LCA: Ancestro Común Menor # Computa para cada nodo de un árbol

# el tiempo de entrada y la profundidad
3.9.1 binary_lifting_funcional.py # y construye un vector a tal que
# min(a[in[u]:in[v]+1]) es el par ordenado
# Dado un grafo funcional # (in[c],c), donde c es el LCA de u y v
# Permite calcular consultas de
# realizar k pasos desde un nodo u def generar(g : list[list[int]], raiz : int = 0) \
# en O(logN). Notar que si en un árbol -> tuple[list[int], list[int], list[int]]:
# cada nodo apunta a su padre tenemos un grafo n = len(g)
# funcional. in_order = [-1]*n
# O(NlogN) en la inicialización depth = [0]*n
# O(logN) por consulta a_vec = []
class BinaryLifting: arista = [0] * n
def __init__(self, f : list[int]): pila = [raiz]
while pila:
self.n = len(f)
u = pila[-1]
self.l = self.n.bit_length()
[Link]()
self.f = [[-1] * self.n for _ in range(self.l)]
if in_order[u] == -1:
self.f[0] = f
in_order[u] = len(a_vec)
for i in range(1, self.l):
a_vec.append((in_order[u],u))
for u in range(self.n):
if arista[u] < len(g[u]):
self.f[i][u] = \
v = g[u][arista[u]]
self.f[i - 1][self.f[i - 1][u]]
arista[u] += 1
# Obtiene f^k(u)
if in_order[v] == -1:
def ksig(self, u : int, k : int) -> int:
depth[v] = depth[u] + 1
for i in range(self.l):
[Link](u)
if k & (1 << i):
[Link](v)
u = self.f[i][u] return in_order, depth, a_vec
return u

Team: –ejemplo–
# Usa Sparse Table
3.9.2 binary_lifting_lca.py class LCA_ST:
# O(NlogN)
# Estructura de datos que almacena el Binary def __init__(self, g : list[list[int]], raiz : int = 0):
# Lifting de un árbol self.n = len(g)
self.in_order, [Link], self.a_vec = generar(g, raiz)
class BinaryLifting: [Link] = st_build(self.a_vec)
def __init__(self, g : list[list[int]], \ def lca(self, u : int, v : int) -> int:
raiz : int = 0, l : int = 0): l, r = self.in_order[u], self.in_order[v]
self.n = len(g) if l > r:
self.l = max(l,self.n.bit_length()) l, r = r, l
[Link] = [[-1] * self.n for _ in range(self.l)] return st_query([Link], l, r)[1]
[Link] = [0] * self.n
[Link][0][raiz] = raiz
Estructuras de Datos

(UNLaM)
pila = [raiz]
while pila:
u = pila[-1]
[Link]() Árbol de Segmentos
for v in g[u]:
if [Link][0][v] == -1:
4.1.1 segment_tree.py
[Link][0][v] = u
[Link][v] = [Link][u] + 1 # Árbol de Segmentos
[Link](v) # Se inicializa con un vector V de n valores
for i in range(1, self.l): # Permite aplicar una operacion op() asociativa a
for u in range(self.n): # un rango [l,r] de V.
[Link][i][u] =\ # Se deben definir:
[Link][i - 1][[Link][i - 1][u]] # * La operación op(a, b)
# * El valor neutro de la operación
def kancestro(self, u : int, k : int) -> int: # Complejidad (llamados a op):
for i in range(self.l): # * Construcción: O(n)
if k & (1 << i): # * Consulta: O(log(n))
u = [Link][i][u] # * Actualización: O(log(n))
return u
class SegmentTree:
def lca(self, u : int, v : int) -> int:
# Ejemplo de posible operacion
if [Link][u] > [Link][v]:
u, v = v, u def Op(self, a, b):
v = [Link](v, [Link][v] - [Link][u]) return a + b
if u == v: # Ejemplo del neutro de la operación
return u neutro = 0
for i in range(self.l - 1, -1, -1): def __init__(self, V):
if [Link][i][u] != [Link][i][v]: # La función __init__ nos permite crear un nuevo elemento de
u = [Link][i][u] la clase
v = [Link][i][v] n = len(V)
Page 7 of 14

return [Link][0][u] [Link] = 1

# El largo que será representado por el árbol de segmentos
def add_hijo(self, p : int) -> None: while [Link] < n:
v = len([Link]) [Link] *= 2
[Link]([p] + [-1] * (self.l - 1)) # Tiene que ser mayor o igual a n
[Link]([Link][p] + 1) [Link] = [neutro for i in range(2 * [Link])]
for i in range(1, self.l): # Crea el árbol inicialmente con el neutro
[Link][i][v] = \ for i in range(n):
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 8 of 14

[Link][[Link] + i] = V[i] # Inicializa las hojas del i //= 2 # Accedo al padre de i

vector while i >= 1:
for i in range([Link] - 1, 0, -1): [Link][i] = [Link]([Link](i*2,[Link]), [Link]

University: Universidad Nacional de La Matanza, DIIT

[Link][i] = Op([Link][i * 2], [Link][i * 2 + 1]) .get(i * 2 + 1,[Link]))
# Inicializa los nodos internos del vector #Actualizo el valor del nodo
i //= 2
def Consulta(self, l, r): # Accedo al padre de i
# Consultas iterativas para mejor performance
# Puede ser la diferencia entre AC y TLE
l += [Link] Sparse Table
r += [Link] 4.2.1 sparse_table.py
lres = [Link]
rres = [Link]
while l <= r: # La Tabla Sparsa es una estructura de datos que permite una
if l % 2 == 1: # inicialización O(NlogN) y consultas en rango:
lres = [Link](lres, [Link][l]) # * Si la operación es idempotente las operaciones son O(1)
l += 1 # * Si la operación no es idempotente las operaciones son O(logN)
if r % 2 == 0: # (Idempotente: f(a,a)=a, ej mínimo, máximo, and, or)
rres = [Link]([Link][r], rres)
r -= 1 def operation(a, b):
l //= 2 return min(a,b)
r //= 2
return [Link](lres, rres) def next_p2(n: int) -> int:
return 1 << (n - 1).bit_length()
def Actualizar(self, i, v):
i += [Link] # Función que recibe un vector y construye su Sparse Table
# La posición i en el vector es i + largo en el árbol # O(NlogN)
[Link][i] = v # Actualiza el valor en la posición i def st_build(v : list[any]) -> list[list[any]]:
i //= 2 # Accedo al padre de i n = len(v)
while i >= 1: k = n.bit_length()
# print(f"Actualizo el nodo {i} accediendo a sus hijos {i st = [[0] * k for _ in range(n)]
*2} e {i*2+1}") for i in range(n):
[Link][i] = Op([Link][i * 2], [Link][i * 2 + 1]) st[i][0] = v[i]
#Actualizo el valor del nodo for j in range(1, k):
i //= 2 # Accedo al padre de i for i in range(n - (1 << j) + 1):

Team: –ejemplo–
st[i][j] = operation(st[i][j - 1], st[i + (1 << (j - 1))][
4.1.2 segment_tree_lazy_creation.py j - 1])
return st
# O(1): Usar si la operación es idempotente (ej: mínimo, máximo, and,
# Árbol de Segmentos or)
# Se inicializa con un entero n que índica el tamaño del def st_query(st : list[list[any]], l : int, r : int) -> any:
# dominio. Inicialmente todos los valores son el neutro j = r - l
# de la operación
k = j.bit_length() - 1
# Permite trabajar con un dominio arbitrariamente grande
return operation(st[l][k], st[r - (1 << k)][k])
# Permite aplicar una operacion op() asociativa a
# un rango [l,r] de V. # O(log(n)): Usar si la operación no es idempotente (ej: suma,
# Se deben definir: producto)
# * La operación op(a, b) def st_query(st : list[list[any]], l : int, r : int) -> any:
# * El valor neutro de la operación res = None
# Complejidad (llamados a op): for k in range(len(st[0]) - 1, -1, -1):

(UNLaM)
# * Construcción: O(n) if l + (1 << k) <= r:
# * Consulta: O(log(n)) if res == None: res = st[l][k]
# * Actualización: O(log(n)) else: operation(st[l][k], st_query(st, l + (1 << k), r))
l += 1 << k
class SegmentTreeLazy: return res
# Ejemplo de posible operacion
def Op(self, a, b):
return a + b
# Ejemplo del neutro de la operación
neutro = 0
Algoritmos
def __init__(self, n): Divide and Conqueer D&C
# La función __init__ nos permite crear un nuevo elemento de
la clase 5.1.1 merge_sort.py
[Link] = 1
while [Link] < n: # Ejemplo de problema resuelto con D&C
[Link] *= 2 # Ordena un vector en O(nlogn)
[Link] = dict() # Realiza log(n) capas de recursión
def Consulta(self, lq, rq, nodo = 1, l = 0, r = - 1): def MergeSort(V : list[any]) -> list[any] :
if r == -1: r = [Link]-1 if len(V) < 2: return V
# Si r no fue dado, se asume que es el largo del árbol - 1 m = len(V) // 2
if l > rq or r < lq or nodo not in [Link]: L = MergeSort(V[:m])
# Si el intervalo [l, r] está completamente fuera de [lq, R = MergeSort(V[m:])
rq] i,j = 0,0
return [Link] for k in range(len(V)):
if lq <= l and r <= rq: if i >= len(L):
# Si el intervalo [l, r] está completamente dentro de [lq, V[k] = R[j]
rq] j += 1
return [Link][nodo] elif j >= len(R):
m = (l + r) // 2 V[k] = L[i]
Page 8 of 14

# Si el intervalo [l, r] está parcialmente dentro de [lq, rq] i += 1

return [Link]([Link](lq, rq, nodo * 2, l, m), self. elif L[i] < R[j]:
Consulta(lq, rq, nodo * 2 + 1, m+1, r)) V[k] = L[i]
i += 1
def Actualizar(self, i, v): else:
i += [Link] # La posición i en el vector es i + largo en V[k] = R[j]
el árbol j += 1
[Link][i] = v # Actualiza el valor en la posición i return V
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM) Page 9 of 14

5.1.2 Teorema Maestro # Solución con 2 punteros al problema

# Dados dos vectores $V_A$ de largo $N$ y $V_B$
Para analizar la complejidad de los algoritmos de

University: Universidad Nacional de La Matanza, DIIT

# de largo $M$ de números enteros, ambos ordenados
Divide y Vencerás (D&C), existen tres técnicas que # en orden creciente.
# Se desea saber para cada elemento de $V_A$
nos pueden ser sumamente útiles: # cuantos elementos de $V_B$ hay menores o iguales
# a él*
• Dividir la recursión en capas: Por ejemplo, en el # O(N+M)
primer problema podemos observar que en cada capa def VectoresParalelos(VA : list[int],VB : list[int]) -> list[int]:
de la recursión hay una complejidad O(n) y que res = [0] * len(VA)
existen log(n) capas, porque en cada una, cada for i in range(len(VA)):
if i : res[i] = res[i-1]
subproblema tiene la mitad del tamaño while res[i] < len(VB) and VB[res[i]] <= VA[i]:
que en la capa anterior. res[i] += 1
return res
• Teorema Maestro: Si en cada paso un problema de
5.2.3 ventana_deslizante.py
tamaño
n se divide en a subproblemas de tamaño # Ejemplo del uso de la técnica de ventana deslizante
n/b y existe un cómputo adicional # para resolver el problema de:
O(f (n)), entonces: # Dado un arreglo de enteros V y un entero k
# determinar para cada subarreglo de longitud k
# la cantidad de elementos distintos
– Si f (n) ∈ O(nc ) con c < logb (a), entonces # O(N * acceso_diccionario)
T (n) ∈ Θ(nlogb (a) ). def Distintos(V : list[int],k : int) -> list[int]:
Ejemplo: T (n) = 8 × T (n/2) + n2 , entonces res = [0] * (len(V)-k+1)
T (n) ∈ O(n3 ). histo = dict()
cantidad = 0
– Si f (n) ∈ Θ(nlogb (a) ), entonces for i in range(k):
T (n) ∈ Θ(nlogb (a) × log n). cantidad += 1 if V[i] not in histo else 0
histo[V[i]] = [Link](V[i],0) + 1
Ejemplo: T (n) = 2 × T (n/2) + n (caso de Merge- res[0] = cantidad
Sort), entonces

Team: –ejemplo–
for i in range(1, len(V)-k+1):
T (n) ∈ Θ(n × log n). j = i+k
cantidad -= 1 if [Link](V[i],0) == 1 else 0
– Si f (n) ∈ Ω(nc ) con c > logb (a) y existe cantidad += 1 if [Link](V[j-1],0) == 0 else 0
k < 1 tal que para n suficientemente grande, histo[V[i]] = [Link](V[i],0) - 1
a × f (n/b) ≤ k × f (n), histo[V[j-1]] = [Link](V[j-1],0) + 1
res[i] = cantidad
entonces T (n) ∈ Θ(f (n)). Ejemplo: return res
T (n) = 2 × T (n/2) + n2 , entonces
T (n) ∈ Θ(n2 ). Algoritmo de Mo
5.3.1 mo_plantilla.py
• Análisis amortizado: Como en otros algoritmos,
puede haber factores que limiten la cantidad # Plantilla para aplicar el algoritmo de Mo a cualquier problema
de estados de manera ad-hoc. En el segundo prob- # Requisitos

(UNLaM)
# - Se realizán consultas de forma asincronica
lema # - No hay actualizaciones
de ejemplo, se observa que cada estado elimina # - La función AgregarElemento debe ser implementada
un elemento, y cada elemento es eliminado por un # - La función EliminarElemento debe ser implementada
# - La variable neutro debe ser definida
único estado. Por lo tanto, hay como máximo n es- # CUIDADO: Si la operación no es conmutativa, deben implementar
tados distintos. # versiones por izquierda y derecha de
# AgregarElemento y EliminarElemento
# para evitar errores
Técnica de 2 Punteros # Complejidad: O((N+Q) * sqrt(N) * O(Agregar/Eliminar Elemento))
# En Python es probable que de TLE, en C++ no debería
5.2.1 dos_punteros.py
# Formato del input: [l,r)

# La técnica de los dos punteros se utiliza def AgregarElemento(actual, elemento):

# para resolver problemas que trabajan con # Recomputa la respuesta al agregar un nuevo elemento
# el conjunto de subarreglos de un arreglo que # ejemplo : return actual + elemento
# cumplen una propiedad X tal que si un subarreglo def EliminarElemento(actual, elemento):
# cumple la propiedad X, cualquier subarreglo # Recomputa la respuesta al eliminar un elemento
# que contenga al subarreglo también cumple la # ejemplo : return actual - elemento
# propiedad X.
def Mo(V : list[int], L : list[int], R:list[int]) -> list[int]:
# Ejemplo de problema resuelto con dos punteros
# Dado un arreglo de enteros no negativos V y N, Q = len(V), len(R)
# un entero k, determinar la cantidad de queries = [(L[i], R[i], i) for i in range(Q)]
# subarreglos de V que suman al menos k. BASE = int(N**0.5)
vec_res = [0] * Q
def DosPunteros(V : list[int],k : int) -> int: [Link](key=lambda x: (x[0]//BASE, x[1]))
res, suma = 0, 0 i, j, res = 0, 0, neutro # Cambiar neutro por el valor neutro de la
L = 0 operación
for R in range(1,len(V)+1): for l, r, idx in queries:
suma += V[R-1] while i < l:
Page 9 of 14

while R > L and suma >= k: res = EliminarElemento(res, V[i])

suma -= V[L] i += 1
L += 1 while i > l:
res += R-L i -= 1
return res res = AgregarElemento(res, V[i])
while j < r:
5.2.2 vectores_paralelos.py res = AgregarElemento(res, V[j])
j += 1
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM)Page 10 of 14

while j > r:
j -= 1 V (GCD(A, B)) = min(V (A), V (B))

University: Universidad Nacional de La Matanza, DIIT

res = EliminarElemento(res, V[j])
vec_res[idx] = res donde el mínimo se toma posición a posición, y
return vec_res

5.3.2 mo_ejemplo.py V (LCM(A, B)) = max(V (A), V (B))

# Utilizar el algoritmo de Mo para resolver

donde el máximo se toma posición a posición.
# el problema de responder consultas de suma Esto nos permite ver por qué GCD (Máximo Común Divi-
# en rango sobre un vector V de enteros sin sor) y LCM (Mínimo Común Múltiplo) tienen propiedades
# actualizaciones
# O((N+Q) * sqrt(N)) análogas a las de mínimo y máximo.
def SumaEnRango(V : list[int], L : list[int], R:list[int]) -> list[int
Divisores
]: 6.2.1 [Link]
N, Q = len(V), len(R)
queries = [(L[i], R[i], i) for i in range(Q)]
# Calcula los divisores de cada número hasta N
BASE = int(N**0.5+1) # O(Nlog(N))
res = [0] * Q
[Link](key=lambda x: (x[0]//BASE, x[1])) def Divisores(N:int) -> list[list[int]]:
i, j, suma = 0, 0, 0 divisores = [ [] for _ in range(N + 1) ]
for l, r, idx in queries: for i in range(1, N + 1):
while i < l: for j in range(i, N + 1, i):
suma -= V[i] divisores[j].append(i)
i += 1 return divisores
while i > l:
i -= 1
suma += V[i] 6.2.2 divisores_un_numero.py
while j < r:
suma += V[j] # Obtiene todos los divisores de un número N
j += 1 # Complejidad: O(sqrt(N))
while j > r:
j -= 1 def DivisoresInd(N :int) -> list[int]:

Team: –ejemplo–
suma -= V[j] divisores = []
res[idx] = suma for i in range(1, N):
return res if i * i > N: # Es mejor que buscar calcular la raiz cuadrada
de antes
break

Matematicas if N % i == 0: # Si i es divisor
[Link](i) # Lo añadimos
if i != N // i: # Si i no es la raiz cuadrada
Números Primos [Link](N // i) # Añadimos el otro divisor
return divisores
6.1.1 criba_eratostenes.py
Divisor Común Mayor
# Calcula la criba de Eratóstenes hasta N 6.3.1 [Link]
# Para cada número 0 <= i <= N, criba[i] es True
# si i es primo, False en caso contrario

(UNLaM)
# O(Nlog(log(N)) # Calcula el Divisor Común Mayor de a y b
# O(log(min(a,b)))
def Eratostenes(N:int) -> list[bool]: # Notar que es una operación:
criba = [False] * 2 + [True] * (N - 1) # - Asociativa
# El 0 y el 1 sabemos que no lo son # - Conmutativa
for p in range(2, N + 1): # - Tiene elemento neutro: 0
# Iteramos los números de 2 a N # - No tiene inverso
if criba[p]: # Si p es primo # - Idempotente (gcd(a,a) = a)
for i in range(p * p, N + 1, p):
# Recorremos de a saltos de longitud p def gcd(a : int, b: int) -> int:
while b != 0:
criba[i] = False a, b = b, a % b
return criba
return a
# para listar primos
primos = Eratostenes(N) Aritmetica Modular
print(list(filter(lambda x: primos[x], range(N+1))))
6.4.1 aritmetica_modular.py
Pensemos que cada número natural (excluido el 0) es
un vector infinito de posiciones naturales (inclu- # Realizar las operaciones con
# los enteros modulo m
ido el 0). En este caso, V (N )[i] indica el exponente
del i-ésimo primo en la factorización del número N . def SumaMod(a, b, m):
return (a+b)%m
Llamemos V (N ) a la representación vectorial de N .
Hacer A × B como números es sumar sus respectivos vec- def RestaMod(a, b, m):
return ((a-b)%m+m)%m
tores. Es decir, V (A × B) = V (A) + V (B).
A

def MultMod(a, b, m):
Análogamente, se tiene que V B = V (A) − V (B). return (a*b)%m
Lo interesante es notar que si un número divide a
otro, entonces tiene un exponente menor o igual en Combinatoria
Page 10 of 14

cada factor primo. Es decir, 6.5.1 [Link]

A | B ⇐⇒ V (A) ≤ V (B) # Factorial: n! = n * (n-1) * (n-2) * ... * 1

# Cantidad de formas de ordenar n elementos
(tomando ≤ posición a posición). # distintos en una fila
# Necesario definir mod
También se puede ver que:
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM)Page 11 of 14

# Usamos memorización para evitar calculos innecesarios # Recordar que sum nos devuelve la suma de todos los elementos de un
_factorial = [1] iterable

University: Universidad Nacional de La Matanza, DIIT

def Factorial(n : int, mod : int) -> int:
def norma(p : list[float]) -> float:
while len(_factorial) <= n: # Retorna la norma de un vector
_factorial.append(MultMod(_factorial[-1],len(_factorial),mod)) return norma2(p)**0.5
return _factorial[n]
# Operar con puntos/vectores
# Combinatoria: nCr = n! / (r! * (n-r)!)
# Cantidad de subconjuntos de tamaño k def suma_puntos(p1 : list[float], p2 : list[float]) -> list[float]:
# de un conjunto de tamaño n # Retorna la suma de dos puntos
# Necesario definir mod return [p1[i] + p2[i] for i in range(len(p1))]

def Combinatoria(n : int, r : int, mod : int) -> int: def producto_por_escalar(p : list[float], k : float) -> list[float]:
if r > n: return 0 # Retorna el producto de un punto por un escalar
return MultMod( return [k * x for x in p]
MultMod(Factorial(n),inv(Factorial(r),mod),mod),
def resta_puntos(p1 : list[float], p2 : list[float]) -> list[float]:
inv(Factorial(n-r),mod),mod)
# Retorna la resta de dos puntos
# Variaciones con Repetición return [p1[i] - p2[i] for i in range(len(p1))]
# Cantidad de formas de elegir r elementos # Recordar que range(n) nos devuelve un iterable con los números del 0
# de un conjunto de n elementos con repetición al n-1
# Necesario definir mod
# Calcular la distancia entre 2 puntos
def VR(n : int, r : int, mod : int) -> int: def distancia(p1 : list[float], p2 : list[float]) -> float:
return PotenciaMod(n, r, mod) # Retorna la distancia entre dos puntos
return norma(resta_puntos(p1, p2))
# Variaciones sin repetición
# Cantidad de formas de elegir r elementos def distancia2(p1 : list[float], p2 : list[float]) -> float:
# de un conjunto de n elementos sin repetición # Retorna el cuadrado de la distancia entre dos puntos
# Necesario definir mod return norma2(resta_puntos(p1, p2))
def V(n : int, r : int, mod : int) -> int: # Calcular el producto punto entre dos vectores
return MultMod(Factorial(n),inv(Factorial(n-r),mod),mod) def producto_punto(p1 : list[float], p2 : list[float]) -> float:
# Retorna el producto punto entre dos puntos
# Permutaciones con repetición
return sum([p1[i] * p2[i] for i in range(len(p1))])
# Cantidad de formas de ordenar un multiconjunto
# con n1, n2, ..., n_k repeticiones de los elementos

Team: –ejemplo–
# Calcular el producto cruz entre dos vectores en R^2
# 1, 2, ..., k def producto_cruz(p1,p2):
def P(ns : list[int], mod : int) -> int: return p1[0]*p2[1]-p1[1]*p2[0]
n = sum(ns) # Calcular el producto cruz entre dos vectores en R^3
res = Factorial(n,mod) def producto_cruz3(p1,p2):
for a in ns: return [p1[1]*p2[2]-p1[2]*p2[1],
res = MultMod(res,inv(Factorial(a,mod),mod),mod) p1[2]*p2[0]-p1[0]*p2[2],
return res p1[0]*p2[1]-p1[1]*p2[0]]
# Recordar:
# Si tengo X con OX ordenes validos e Y con OY 6.6.2 poligono_convexo.py
# ordenes validos, puedo unirlos y si no hay
# restrcciones entre sus elementos
# (X U Y) tiene C(|X|+|Y|,|X|) * OX * OY ordenes # Funciones para trabajar con poligonos convexos
# validos # Dados los puntos de un poligono convexo en orden anti-horario

(UNLaM)
# retorna el area del poligono. (Si están en sentido
6.5.2 Precomputo O(N ) # horario el area es negativa)
def Area_Poligono(puntos): # se asumen ordenados
p = puntos[0]
# Dado un N y un modulo mod, computa en O(N)
# los factoriales y sus inversos modulo mod return sum(producto_cruz(resta_punto(puntos[i],p),
# hasta N inclusive resta_punto(puntos[(i+1)%len(puntos)],p))
# idea: [Link] for i in range(len(puntos)))/2
# O(N) # Calcula si un punto está dentro de un poligono convexo
def precomputo(N : int, mod : int): # Asume que los puntos están ordenados en sentido horario
fact = [1] * (N+1) # o anti-horario
inv = [1] * (N+1) # O(N)
inv_fact = [1] * (N+1) def PuntoEnPoligono(p,puntos):
for i in range(2,N+1): for i in range(len(puntos)):
fact[i] = (fact[i-1] * i) % mod p_i = puntos[i]
inv[i] = (mod - (mod // i) * inv[mod % i]) % mod p_ip1 = puntos[(i+1)%len(puntos)]
inv_fact[i] = (inv_fact[i-1] * inv[i]) % mod area = producto_cruz(resta_punto(p_i,p),resta_punto(p_ip1,p))
# fact[i] = factorial de i if area<0:
# inv[i] = inverso de i return False
# inv_fact[i] = inverso del factorial de i return True
return fact, inv, inv_fact
Capsula Convexa
Elementos de Geometría 6.7.1 capsula_convexa.py
6.6.1 [Link]
# Calcula la Capsula Convexa de un conjunto
# En esta archivo están las funciones para trabajar # de puntos en el plano
# con puntos/vectores. # La capsula convexa es el mínimo poligono
# Un vector en R^n es una lista de n números reales # convexo que contiene todos los puntos
# Es mínima en, al menos, los siguientes sentidos
Page 11 of 14

# Un punto en R^n es un vector en R^n

# Ej: Un punto en R^2 es una lista de 2 números reales # - Minima area
# Ej: Un punto en R^3 es una lista de 3 números reales # - Minimo perimetro
# - Está incluida en cualquier otro poligono
# convexo que contenga todos los puntos
# Calcular la norma (tamaño) de un vector en R^n
def norma2(p : list[float]) -> float: # Esta es una implementación distinta a la vista en clase
# Retorna el cuadrado de la norma de un vector # porque es mucho más eficiente y soporta mejor tener 3 o más
return sum([x**2 for x in p]) # puntos colineales
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM)Page 12 of 14

(Möbius Inv. Formula) Let

# Complejidad: O(n log n)
# Necesita tener implementadas las funciones de [Link]

University: Universidad Nacional de La Matanza, DIIT

X
g(n) = f (d), then
def angulo(a, b, c): d|n
return (a[0] * (b[1] - c[1]) +
b[0] * (c[1] - a[1]) + X n
c[0] * (a[1] - b[1])) f (n) = g(d)µ
d
d|n
def CapsulaConvexa(puntos):
puntos = [Link]()
if len(puntos) <= 3:
Rodrigues Rotation Formula
return puntos Rodrigues rotation formula (rota v alrededor de z vec-
[Link]() tor unitario, segun un angulo θ:
cap = []
# En la comparativa poner >0 para incluir puntos alineados
# Poner >=0 para excluir puntos alineados vrot = v cos θ + (z × v) sin θ + z(z · v)(1 − cos θ)
for p in puntos:
while len(cap)>1 and angulo(cap[-2],cap[-1],p)>0: Convoluciones Rápidas
[Link]()
[Link](p) 6.11.1 [Link]
[Link]()
[Link]() import cmath
for p in puntos:
while len(cap)>1 and angulo(cap[-2],cap[-1],p)>0: # FFT function from previous implementation
[Link]() def fft(a):
[Link](p) n = len(a)
return cap if n <= 1:
return a
# usar cap, puntos = CapsulaConvexa(ps) para obtener la capsula
convexa even = fft(a[0::2])
# y los puntos ordenados. odd = fft(a[1::2])
T = [[Link](-2j * [Link] * k / n) * odd[k] for k in range(n
Teoría de juegos // 2)]

Team: –ejemplo–
6.8.1 [Link] return [even[k] + T[k] for k in range(n // 2)] + \
[even[k] - T[k] for k in range(n // 2)]
# Calcular el mínimo entero no negativo excluido
# de un iterable. def ifft(a):
# Importante porque el número de Grundy de un estado # Compute the inverse FFT by taking the FFT of the complex
# de un juego es el MEX de los Grundy de los estados conjugate,
# a los que se puede llegar. # scaling the result, and taking the complex conjugate again.
# O(N) n = len(a)
a_conj = [[Link]() for x in a]
def MEX(iterable): y = fft(a_conj)
n = len(iterable) return [([Link]() / n) for x in y]
esta = [False] * (n+1)
for i in iterable: def convolve(x, y):
if i <= n: # Length of the result after convolution
esta[i] = True n = len(x) + len(y) - 1

(UNLaM)
mex = 0 # Pad x and y with zeros to length n
while mex<n and esta[mex]: x_padded = x + [0] * (n - len(x))
mex += 1 y_padded = y + [0] * (n - len(y))
return mex
# Compute the FFT of both sequences
# Versión más corta pero menos performante
# por utilizar un set fft_x = fft(x_padded)
def MEX_byCopilot(iterable): fft_y = fft(y_padded)
mex = 0 # Point-wise multiplication of the FFTs
conjunto = set(iterable) fft_product = [a * b for a, b in zip(fft_x, fft_y)]
while mex in conjunto:
mex += 1 # Compute the inverse FFT to get the convolution result
return mex result = ifft(fft_product)
# Since the output may have small imaginary parts due to numerical
Identities errors, return the real part
Cn = 2(2n−1)
n+1
Cn−1 return [round([Link]) for r in result]
1 2n
Cn = n+1 n 6.11.2 [Link]
4n√
Cn ∼ n3/2 π
F2n+1 = Fn2 + Fn+1
2 def ntt(a, n, p, g):
2 2 # Aplica la Transformada Número Teórico (NTT) a la secuencia a
P2nn = Fn+1 − Fn−1
F result = a[:]
i=1 Fi = Fn+2 − 1 for length in range(1, n, 2):
Fn+i Fn+j − Fn Fn+i+j = (−1)n Fi Fj w_n = pow(g, (p - 1) // (2 * length), p)
Pn i r n+1 −1 w = 1
i=0 r = r−1 for start in range(0, n, 2 * length):
Pn 2 n·(n+1)·(2n+1) for i in range(length):
i=1 i = 6 u = result[start + i]
Pn 3  n·(n+1) 2 v = (result[start + i + length] * w) % p
i=1 i =
Page 12 of 14

2 result[start + i] = (u + v) % p
Pn 4 n·(n+1)·(2n+1)·(3n2 +3n−1) result[start + i + length] = (u - v) % p
i=1 i = 12
Pn 5  n·(n+1) 2 2n2 +2n−1 w = (w * w_n) % p
· return result
i=1 i = 2 3
Pn n−1
n−1 def intt(a, n, p, g):
= 2
Pi=1
n
i−1
n−1

n−1
# Aplica la Transformada Número Teórico Inversa (INTT)
i=1 i · i−1 = n · 2 n_inv = pow(n, p - 2, p) # Inversa de n módulo p
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM)Page 13 of 14

g_inv = pow(g, p - 2, p) # Inversa de g módulo p # valores de z iguales a la longitud de T

# Complejidad: O(n)
result = ntt(a, n, p, g_inv)

University: Universidad Nacional de La Matanza, DIIT

return [(x * n_inv) % p for x in result] def array_z(S : str) -> list[int]:
l, r, n = 0, 0, len(S)
def next_power_of_2(x): z = [0]*n
# Calcula la siguiente potencia de 2 mayor o igual a x
# z[i] = max k: s[0,k) == s[i,i+k)
return 1 << (x - 1).bit_length() for i in range(1, n):
def convolve_ntt(a, b, p, g): # Invariante: s[0,r-l) == s[l,r)
# Realiza la convolución usando NTT sin asumir que el tamaño es if i <= r:
potencia de 2 z[i] = min(r - i + 1, z[i - l])
n = len(a) + len(b) - 1 while i + z[i] < n and S[z[i]] == S[i + z[i]]:
n_padded = next_power_of_2(n) z[i] += 1
if i + z[i] - 1 > r:
# Rellena las secuencias con ceros hasta la siguiente potencia de l, r = i, i + z[i] - 1
2 z[0] = len(S)
a_padded = a + [0] * (n_padded - len(a)) # Por convención puede ser z[0] = 0
b_padded = b + [0] * (n_padded - len(b)) return z
# Aplica NTT a ambas secuencias # array_z("xaxbxxax")
ntt_a = ntt(a_padded, n_padded, p, g) # [8, 0, 1, 0, 1, 3, 0, 1]
ntt_b = ntt(b_padded, n_padded, p, g)
# Multiplicación punto a punto
Manacher (Palindromos)
ntt_c = [(x * y) % p for x, y in zip(ntt_a, ntt_b)] 7.3.1 [Link]
# Aplica la NTT inversa
result = intt(ntt_c, n_padded, p, g) # Dado un string S, la función Manacher(S) devuelve
# dos listas de enteros de longitud n, donde n es la
# Trunca al tamaño real del resultado de la convolución # longitud de S. La primera lista es impar y la segunda
return result[:n] # es par. La lista impar[i] es la longitud del palíndromo
# Ejemplo de uso # más largo con centro en S[i] y la lista par[i] es la
# a = [1, 2, 3] # longitud del palíndromo más largo con centro en el
# b = [4, 5, 6] # espacio entre S[i-1] y S[i].
# p = 998244353 # Un número primo #
# Es decir, impar[i] es el máximo k tal que S[i-k:i+k]

Team: –ejemplo–
# g = 3 # Una raíz primitiva módulo 998244353
# es un palindromo y par[i] es el máximo k tal que
#result = convolve_ntt(a, b, p, g) # S[i-k:i+k) es un palindromo.
#
# Recordar que un palindromo es una cadena que se lee

Strings #
#
#
igual de izquierda a derecha que de derecha a izquierda.

O(n).
Bordes def Manacher(S : str) -> tuple[list[int],list[int]]:
7.1.1 [Link] n = len(S)
par, impar = [0]*n, [0]*n
l, r = 0, -1
# Calcula el array de bordes de un string
# Un borde es un substring propio que es for i in range(n):
# tanto prefijo como sufijo k = 1 if i>r else min(impar[l+r-i],r-i)

(UNLaM)
# bordes[i] = k => s[:k) es el mayor borde de s[:i) while i+k<n and i-k>=0 and S[i+k]==S[i-k]:
# Complejidad: O(n) k+=1
k -= 1
# Notar que podemos obtener las apariciones de un impar[i] = k
# string T en un string S calculando if i+k>r: l, r = i-k, i+k
# bordes(T + "#" + S) y contando las apariciones
l,r = 0, -1
# de T en los bordes
for i in range(n):
def bordes(S : str) -> list[int]: k = 1 if i>r else min(par[l+r-i+1],r-i+1)+1
bordes = [0] * len(S) while i+k<=n and i-k>=0 and S[i+k-1]==S[i-k]:
for i in range(1, len(S)): k+=1
# Invariante: bordes[0:i) ya computados k -= 1
j = bordes[i - 1] par[i] = k
while j > 0 and S[i] != S[j]: if i+k-1>r: l, r = i-k, i+k-1
j = bordes[j - 1] return impar, par
if S[i] == S[j]: #Ejemplo
j += 1 #S = "aabbaacaabbaa"
bordes[i] = j #impar, par = Manacher(S)
return [0] + bordes #print(impar)
# para que coincida con la convención #[0, 0, 0, 0, 0, 0, 6, 0, 0, 0, 0, 0, 0]
# bordes("abacaba") #print(par)
# [0, 0, 1, 0, 1, 2, 3, 0] #[0, 1, 0, 3, 0, 1, 0, 0, 1, 0, 3, 0, 1]

Función Z Trie
7.2.1 funcion_z.py 7.4.1 [Link]

# Implementación de la estructura Trie

# Calcula la función z de un string # Un Trie es un árbol donde cada nodo tiene
# La función z de un string S es un arreglo # un diccionario de caracteres a nodos y un contador
Page 13 of 14

# de longitud n tal que z[i] es la longitud # de cuantas veces se ha pasado por ese nodo
# del string más largo que comienza en S[i] # O(|S|) para todas las operaciones
# que es prefijo de S
# Es decir, el Prefijo Común Mayor entre T = [[0, dict()]] # (acumulador, hijos)
# S y S[i:] # Puede modificarse para guardar metadata adicional
# Se puede utilizar para encontrar todas las
# ocurrencias de un string T en S # Agrega la cadena S al trie T
# Calculando z(T + "#" + S) y buscando los def Agregar(T : list[tuple[int,dict[str,int]]], S : str) -> int:
 University: Universidad Nacional de La Matanza, DIIT Team: –ejemplo– (UNLaM)Page 14 of 14

nodo = 0 = 145152 ; σ1 (37800) = 148800 ; σ1 (60480) = 243840 ;

for c in S: σ1 (64680) = 246240 ; σ1 (65520) = 270816 ; σ1 (70560)
if c not in T[nodo][1]:

University: Universidad Nacional de La Matanza, DIIT

T[nodo][1][c] = len(T) = 280098 ; σ1 (95760) = 386880 ; σ1 (98280) = 403200 ;
[Link]([0, dict()]) σ1 (100800) = 409448 ; σ1 (491400) = 2083200 ;
T[nodo][0] += 1 σ1 (498960) = 2160576 ; σ1 (514080) = 2177280 ; σ1 (982800)
nodo = T[nodo][1][c]
T[nodo][0] += 1 = 4305280 ; σ1 (997920) = 4390848 ; σ1 (1048320) = 4464096
return nodo ; σ1 (4979520) = 22189440 ; σ1 (4989600) = 22686048 ;
# Borra la cadena S del trie T σ1 (5045040) = 23154768 ; σ1 (9896040) = 44323200 ;
def Borrar(T : list[tuple[int,dict[str,int]]], S : str) -> int: # σ1 (9959040) = 44553600 ; σ1 (9979200) = 45732192
Asume que S está representado en T
nodo = 0 Factoriales
for c in S:
T[nodo][0] -= 1
0! = 1 11! = 39.916.800
nodo = T[nodo][1][c] 1! = 1 12! = 479.001.600 (∈ int)
T[nodo][0] -= 1 2! = 2 13! = [Link]
return nodo
3! = 6 14! = [Link]
# Busca la cadena S en el trie T 4! = 24 15! = [Link].000
def Buscar(T : list[tuple[int,dict[str,int]]], S : str) -> int:
nodo = 0 5! = 120 16! = [Link].000
for c in S: 6! = 720 17! = [Link].000
if c not in T[nodo][1]:
return None 7! = 5.040 18! = [Link].728.000
nodo = T[nodo][1][c] 8! = 40.320 19! = [Link].832.000
return nodo 9! = 362.880 20! = [Link].176.640.000 ∈ ll
10! = 3.628.800 21! = [Link].709.400.000

Other max signed tint =

max unsigned tint
[Link].854.775.807
= [Link].709.551.615

Tablas y Cotas Consejos

Team: –ejemplo–
Primos cercanos a 10n Debugging
9941 9949 9967 9973 10007 10009 10037 10039 10061 • ¿Si n = 0 anda? (similar casos borde tipo n=1,
10067 10069 10079 n=2, etc)
99961 99971 99989 99991 100003 100019 100043 100049
100057 100069 • ¿Si hay puntos alineados anda?
999959 999961 999979 999983 1000003 1000033 1000037 • ¿Si es vacío anda?
1000039 • ¿Si hay multiejes anda?
9999943 9999971 9999973 9999991 10000019 10000079
• ¿Si no tiene aristas anda?
10000103 10000121
99999941 99999959 99999971 99999989 100000007 100000037 • ¿Si tiene ciclos anda?
100000039 100000049 • ¿Si tiene un triángulo anda?

(UNLaM)
999999893 999999929 999999937 1000000007 1000000009 • ¿Los arrays son suficientemente grandes? (siempre
1000000021 1000000033 denle bastante de más por las dudas, pero tampoco
se ceben como para que ya no entre en memoria XD)
Cantidad de primos menores que 10n • ¿Puede dar integer overflow? (SIEMPRE mirar el
π(101 ) = 4 ; π(102 ) = 25 ; π(103 ) = 168 ; π(104 ) = 1229 integer overflow con MUCHO cuidado)
; π(105 ) = 9592 ; π(106 ) = 78.498 ; π(107 ) = 664.579 ;
• ¿Podés dividir por cero en algún caso?
π(108 ) = 5.761.455 ; π(109 ) = 50.847.534 ;
π(1010 ) = 455.052,511 ; π(1011 ) = [Link] ; • ¿Estás memorizando la recursión bien?
π(1012 ) = [Link] • ¿El caso base está bien hecho y se llega siempre?
Divisores • ¿Están bien puestas las cotas iniciales de la bi-
0 nary / inicialización del acumulador máximo/mín-
Cantidad de divisores (σ0 ) para algunos n/¬∃n <
n, σ0 (n0 ) > σ0 (n) imo?
σ0 (60) = 12 ; σ0 (120) = 16 ; σ0 (180) = 18 ; σ0 (240) • ¿Estás inicializando bien antes de cada caso?
= 20 ; σ0 (360) = 24 ; σ0 (720) = 30 ; σ0 (840) = 32 • ¿Le copiaste el input dos veces en el archivo de
; σ0 (1260) = 36 ; σ0 (1680) = 40 ; σ0 (10080) = 72 ; entrada (para ver que de igual y bien las dos ve-
σ0 (15120) = 80 ; σ0 (50400) = 108 ; σ0 (83160) = 128 ; ces)? [No aplica cuando viene solo una instancia
σ0 (110880) = 144 ; σ0 (498960) = 200 ; σ0 (554400) = 216 de input]
; σ0 (1081080) = 256 ; σ0 (1441440) = 288 σ0 (4324320) =
384 ; σ0 (8648640) = 448 • ¿Pasa los ejemplos? [No es joda, Leo se quedo
Suma de divisores (σ1 ) para algunos n/¬∃n0 < n, σ1 (n0 ) > afuera de la mundial por esto]
σ1 (n) ; σ1 (96) = 252 ; σ1 (108) = 280 ; σ1 (120) = 360 Hitos de prueba
Page 14 of 14

; σ1 (144) = 403 ; σ1 (168) = 480 ; σ1 (960) = 3048 ; • 45min todas las columnas de la tabla llena
σ1 (1008) = 3224 ; σ1 (1080) = 3600 ; σ1 (1200) = 3844
; σ1 (4620) = 16128 ; σ1 (4680) = 16380 ; σ1 (5040) = • 2h todos conocen todo
19344 ; σ1 (5760) = 19890 ; σ1 (8820) = 31122 ; σ1 (9240)
• 3h reunión estratégica
= 34560 ; σ1 (10080) = 39312 ; σ1 (10920) = 40320 ;
σ1 (32760) = 131040 ; σ1 (35280) = 137826 ; σ1 (36960) • 4h reunión estratégica