El Martillo y la Trampa

En los dominios del Imperio Algorítmico, los grandes problemas nunca se resuelven de frente. Los maestros de la Orden enseñan la misma verdad desde hace siglos: “divide el problema en subproblemas más pequeños, resuélvelos por separado, y combina las soluciones”.

Esta guía recorre seis desafíos del mundo del Imperio. Algunos te pedirán plantear una solución, otros te darán código para analizar o completar, y uno o dos son trampas: situaciones donde división y conquista no es la herramienta correcta.

Aprendé a reconocer cuándo usar el martillo… y cuándo buscar otra herramienta.

El Mensajero y el Río de Cristal
El mensajero Aldric debe cruzar el Río de Cristal, dividido en $n$ secciones. Cada sección tiene una altura de corriente. Aldric necesita encontrar la sección con la corriente más alta para evitarla. No tiene tiempo de recorrer todo el río: debe hacerlo en el menor tiempo posible.

Enunciado

Dado un arreglo de $n$ enteros que representa las alturas de corriente de cada sección del río, plantea un algoritmo de división y conquista para encontrar el valor máximo.
1. Describir el caso base y el paso recursivo en palabras.
2. Escribir la recurrencia de tiempo $T (n)$ .
3. Usar el Teorema Maestro para resolverla y obtener la complejidad final.
4. ¿Es esta una mejora respecto a una búsqueda lineal? Justificar.
Pista del Sabio Ermitage: La recurrencia que encontrarás es $T (n) = 2 \cdot T (n /2) + O (1)$ . El trabajo de combinar dos soluciones (comparar dos máximos) es constante. Aplica el Caso 1 del Teorema Maestro.

Reflexión Trampa. Antes de responder el punto 4, pensalo bien: ¿obtener el máximo con división y conquista es asintóticamente mejor que un simple recorrido lineal? ¿Por qué alguien lo usaría (o no)?
Ver solución

1. Caso base y paso recursivo
- Caso base: una sección de un solo elemento; ese elemento es el máximo.
- Paso recursivo: dividir el array en dos mitades, calcular el máximo de cada una por separado, y combinar quedándose con el mayor de los dos.
Esto funciona porque el máximo global siempre coincide con el máximo de alguna de las dos mitades.

2. Algoritmo
```
def encontrar_maximo(alturas, izq, der):
    if izq == der:                 # caso base
        return alturas[izq]
 
    medio = (izq + der) // 2
    max_izq = encontrar_maximo(alturas, izq, medio)
    max_der = encontrar_maximo(alturas, medio + 1, der)
 
    return max(max_izq, max_der)   # combinar: O(1)
```
Nota: se pasan índices (izq, der) en vez de hacer slicing (arr[:medio]). Si se hiciera slicing, cada división copiaría el array y costaría $O (n)$ , cambiando la recurrencia.

3. Recurrencia y Teorema Maestro

Dividir es $O (1)$ , hay 2 subproblemas de tamaño $n /2$ , y combinar (una comparación) es $O (1)$ :

$T (n) = 2 \cdot T (n /2) + O (1)$

Con $a = 2, b = 2, f (n) = O (1)$ : el exponente crítico es $n^{l o g_{2} 2} = n$ . Como $f (n) = O (1)$ es polinomialmente menor que $n$ , aplica el Caso 1 del Teorema Maestro:

$T (n) = Θ (n)$

4. ¿Es una mejora respecto a la búsqueda lineal?

No. Un recorrido lineal simple también es $Θ (n)$ : dividir y combinar acá no elimina trabajo, solo lo reorganiza. La ventaja de D&C no es automática, sino que solo mejora la complejidad cuando el paso de dividir/combinar ahorra algo real (como en Merge Sort). Acá no hay ahorro, por eso ambos enfoques quedan en la misma clase asintótica.

¿Entonces para qué serviría igual? Porque las dos mitades son independientes entre sí, se podrían calcular en paralelo (algo que un recorrido lineal secuencial no ofrece naturalmente). En la práctica, sin paralelismo, el recorrido lineal suele ser incluso más rápido (menos overhead de llamadas recursivas).
Abrir artículo
El Archivo Roto del Archiduque
El Archiduque Vorn custodia el Gran Archivo: una lista de n pergaminos ordenados por fecha. Un aprendiz los mezcló y ahora están en desorden. El Archiduque necesita reordenarlos, pero el archivo es enorme y los métodos simples de los escribas son demasiado lentos. Un antiguo grimorio describe el Método del Espejo Partido: “divide la pila en dos, ordena cada mitad, y luego combínalas”. Según el Sabio Ermitage, esto se conoce como Merge Sort. El aprendiz copió el código… pero dejó tres partes sin terminar.

Enunciado

Completá la función merge_sort y su auxiliar merge. Los fragmentos marcados con # ??? son los que debes implementar.
```
def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        # ??? Compara left[i] y right[j].
        # Agrega el menor a result y avanza el índice correspondiente.
        # ???
 
    # ??? Agrega los elementos restantes de ambas mitades.
    # ???
    return result
 
 
def merge_sort(arr):
    if len(arr) <= 1:
        return arr               # caso base
 
    mid = ## ???                 # ??? Calcula el punto de división
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)
 
 
# Prueba:
pergaminos = [38, 27, 43, 3, 9, 82, 10]
print(merge_sort(pergaminos))
# Esperado: [3, 9, 10, 27, 38, 43, 82]
```
Guía del Sabio Ermitage: Para merge: cuando termina el while, al menos una lista está vacía. Puedes extender result con la cola de cada una. Para mid: el punto medio es len(arr) // 2.

Una vez que funcione, respondé: ¿cuál es la complejidad temporal y espacial de Merge Sort? ¿Qué aporta el paso de combinar comparado con el de dividir?
Abrir artículo
La Profecía de los Mercaderes
Los mercaderes del Imperio registran el precio de la Gema Celeste día a día. Un vidente afirma que si comprás la gema en el día i y la vendés en el día j (con i < j), podés maximizar tu ganancia. Pero con siglos de registros, los mercaderes necesitan un algoritmo eficiente: buscar todas las parejas (i, j) es demasiado lento.

Enunciado: Máxima Ganancia por Subarray

Dado un arreglo precios[0..n-1], encuentra el par de índices (i, j) con i < j que maximiza precios[j] - precios[i].
1. Enfoque fuerza bruta: describir el algoritmo $O (n^{2})$ sin codificarlo.
2. Enfoque división y conquista: el truco está en que al dividir el arreglo en dos mitades, la ganancia máxima puede venir de (a) solo la mitad izquierda, (b) solo la mitad derecha, o (c) comprando en la mitad izquierda y vendiendo en la derecha. Plantear cómo calcular el caso (c) eficientemente.
3. Escribir la recurrencia y determinar la complejidad.
Consejo del Sabio Ermitage: El caso (c) se resuelve con el mínimo de la mitad izquierda y el máximo de la mitad derecha. Ambos pueden calcularse en $O (n)$ en total. La recurrencia resultante es $T (n) = 2 \cdot T (n /2) + O (n)$ . ¿A qué caso del Teorema Maestro corresponde?

Variante (opcional): ¿Cómo cambiaría la solución si el arreglo representara ganancias diarias (pueden ser negativas) y se quisiera el subarreglo contiguo de suma máxima? Este problema se conoce como Maximum Subarray. ¿Coincide la recurrencia?

Abrir artículo

El Contador de Traidores
El Senado Imperial lleva un registro de n lealtades, cada una un entero. Dos lealtades (i, j) forman una inversión si i < j pero lealtad[i] > lealtad[j]: un superior en la lista tiene menos lealtad que un subordinado, señal de corrupción. El Senado necesita contar cuántas inversiones hay para detectar el nivel de traición… pero n puede ser enorme.

Enunciado: Contar Inversiones

Implementar una función contar_inversiones(arr) que devuelva el número de pares (i, j) con i < j y arr[i] > arr[j].

Restricción: debe hacerse en $O (n lo g n)$ , no en $O (n^{2})$ .

Pista del Sabio Ermitage: modificar Merge Sort. Durante el paso de merge, cuando se toma un elemento de la mitad derecha antes que uno de la izquierda, ¿cuántas inversiones se estan “descubriendo” en ese momento?
def merge_contar(left, right):
    # Combina left y right ordenadamente.
    # Cuenta las inversiones que "cruzan" la división.
    result = []
    inversiones = 0
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            result.append(left[i]); i += 1
        else:
            # left[i] > right[j] → inversión
            # ??? ¿cuántas inversiones agrega este paso?
            result.append(right[j]); j += 1
    result += left[i:] + right[j:]
    return result, inversiones
 
def contar_inversiones(arr):
    if len(arr) <= 1:
        return arr, 0
    mid = len(arr) // 2
    left,  inv_l = contar_inversiones(arr[:mid])
    right, inv_r = contar_inversiones(arr[mid:])
    merged, inv_m = merge_contar(left, right)
    return merged, inv_l + inv_r + inv_m
Probar con [2, 4, 1, 3, 5]. Las inversiones son (2,1), (4,1), (4,3): el resultado debe ser 3. Verificar la implementación y explicar por qué el conteo en merge_contar es correcto.
Abrir artículo

La Torre de los Ecos Infinitos y el Engaño del Oráculo
En la Torre de los Ecos Infinitos, también conocida como Torre de Fibonacci, un oráculo falso convence a los aprendices de que todo puede resolverse con división y conquista. “¡Divide el problema!”, grita. Pero el sabio Ermitage sabe que algunos problemas tienen una estructura donde dividir y reconquistar crea más trabajo del que ahorra. El oráculo presenta el cálculo del n-ésimo número de Fibonacci como candidato perfecto para división y conquista recursivo. Ermitage sonríe… y deja que los aprendices descubran el error por sí mismos.

Enunciado: Fibonacci Recursivo Ingenuo

Considerar esta implementación “división y conquista” de Fibonacci:
```
def fib_dc(n):
    if n <= 1:
        return n                          # caso base
    return fib_dc(n - 1) + fib_dc(n - 2)  # "divide" en dos subproblemas
```
Responder las siguientes preguntas:
1. ¿Es esto realmente división y conquista? Describir qué condición fundamental de DyC no se cumple aquí (pensar en la independencia de los subproblemas).
2. Complejidad: trazar el árbol de llamadas para fib(6). ¿Cuántas veces se calcula fib(2)? Escribir la recurrencia y determina que la complejidad es $O (2^{n})$ .
3. Solución correcta: reescribir fib(n) usando otra técnica y demostrar que es $O (n)$ .
4. Reflexión: ¿en qué se diferencia “división y conquista” de “programación dinámica”? ¿Cuándo se usa cada una?
Lección del Sabio Ermitage: División y conquista funciona bien cuando los subproblemas son independientes. Cuando se solapan, dividir y reconquistar sin memoria repite trabajo exponencialmente. La herramienta correcta en esos casos es la programación dinámica.
Ver solución

1. ¿Es esto realmente división y conquista?

No, no en el sentido que importa. Tiene la forma superficial de D&C (caso base + dos llamadas recursivas + combinar sumando), pero le falta la condición fundamental: que los subproblemas sean independientes.

fib_dc(n-1) internamente vuelve a calcular fib_dc(n-2), fib_dc(n-3), etc. que son los mismos subproblemas que ya se están calculando por otro lado, en la rama de fib_dc(n-2). No son subproblemas disjuntos que se resuelven una única vez: se solapan y se recalculan una y otra vez. Ese solapamiento es lo que rompe la premisa de D&C.

2. Complejidad

Árbol de llamadas para fib(6) (abreviado; los subárboles idénticos se repiten):
```
fib(6)
├── fib(5)
│   ├── fib(4)
│   │   ├── fib(3)
│   │   │   ├── fib(2) → fib(1), fib(0)
│   │   │   └── fib(1)
│   │   └── fib(2) → fib(1), fib(0)
│   └── fib(3)
│       ├── fib(2) → fib(1), fib(0)
│       └── fib(1)
└── fib(4)
    ├── fib(3)
    │   ├── fib(2) → fib(1), fib(0)
    │   └── fib(1)
    └── fib(2) → fib(1), fib(0)
```
fib(2) aparece 5 veces, calculado desde cero cada vez. Eso es el solapamiento del punto 1, hecho concreto.

Recurrencia:

$T (n) = T (n - 1) + T (n - 2) + O (1)$

Por qué es $O (2^{n})$ : como $T (n - 2) \leq T (n - 1)$ , se puede acotar $T (n) \leq 2 \cdot T (n - 1) + O (1)$ . Desenrollando esa cota (o por inducción: si $T (k) \leq c \cdot 2^{k}$ vale para todo $k < n$ , entonces $T (n) \leq c \cdot 2^{n - 1} + c \cdot 2^{n - 2} + O (1) \leq c \cdot 2^{n}$ ), se obtiene $T (n) = O (2^{n})$ .

Dato extra para quien quiera precisión: la cota ajustada es en realidad $Θ (φ^{n})$ , con $φ \approx 1.618$ el número áureo, más lento que lineal, pero algo menor que $2^{n}$ . $O (2^{n})$ sigue siendo una cota superior válida y mucho más simple de demostrar.

3. Solución correcta: $O (n)$

Con programación dinámica (versión iterativa, sin recalcular nada):
```
def fib_dp(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b
```
El for corre $n - 1$ veces, cada iteración es $O (1)$ → $T (n) = O (n)$ , y $O (1)$ de memoria extra.

(Alternativa equivalente en espíritu: memoización top-down, guardando cada fib(k) calculado en un map para no repetirlo. También $O (n)$ , porque cada subproblema se resuelve una sola vez.)

4. División y conquista vs. programación dinámica
- D&C: los subproblemas son independientes: no se solapan entre sí. Se resuelven una vez cada uno y se combinan. Ejemplos: Merge Sort, búsqueda binaria, Karatsuba.
- Programación dinámica: los subproblemas se solapan (el mismo subproblema aparece en múltiples ramas de la recursión). La clave es guardar cada resultado la primera vez que se calcula, para no repetir trabajo. Ejemplos: Fibonacci, camino mínimo, mochila.
Regla práctica: si al dibujar el árbol de recursión aparecen nodos repetidos → programación dinámica. Si todos los subproblemas son distintos → división y conquista.
Abrir artículo
El Torneo de las Casas Gemelas
Las Casas Gemelas del Imperio celebran el Gran Torneo cada siglo. Cada casa tiene exactamente n guerreros (con n potencia de 2). El árbitro necesita organizar un torneo donde cada guerrero de la Casa Norte compita contra exactamente un guerrero de la Casa Sur. Pero los emparejamientos deben hacerse de forma que ningún guerrero compita más de una vez, y la asignación debe hacerse en tiempo $O (n lo g n)$ . El árbitro recuerda haber visto este patrón antes… en los pergaminos de multiplicación de polinomios.

Enunciado: Multiplicación de Polinomios / Introducción a FFT

Dados dos polinomios de grado n-1 representados como arreglos de coeficientes:
```
A = [a₀, a₁, ..., aₙ₋₁]    B = [b₀, b₁, ..., bₙ₋₁]
```
Su producto C = A × B es un polinomio de grado 2n-2.
1. Método naïve: la multiplicación directa toma $O (n^{2})$ . Descríbela brevemente.
2. Algoritmo de Karatsuba: en lugar de 4 multiplicaciones para dividir el polinomio en mitades, Karatsuba usa solo 3. Explica la idea central: si A = A_hi·x^(n/2) + A_lo y lo mismo para B, ¿cómo calcular los tres productos necesarios y combinarlos?
3. Escribe la recurrencia de Karatsuba: $T (n) = 3 \cdot T (n /2) + O (n)$ . Aplica el Teorema Maestro y obtén $O (n^{l o g_{2} 3}) \approx O (n^{1.585})$ .
4. (Desafío, no obligatorio): investigar brevemente cómo la FFT (Fast Fourier Transform) lleva esto aún más lejos hasta $O (n lo g n)$ . ¿Qué representa “evaluar el polinomio en raíces de la unidad” en el contexto del Torneo de las Casas?
Método Complejidad Paradigma
Multiplicación naïve $O (n^{2})$ Fuerza bruta
Karatsuba $O (n^{1.585})$ División y Conquista
FFT / NTT $O (n lo g n)$ División y Conquista + matemática

Reflexión final: Este ejercicio muestra el poder real de división y conquista: no solo ordena arreglos, sino que puede reducir el número de operaciones fundamentales (multiplicaciones) de 4 a 3, lo cual parece trivial hasta que se eleva a escala logarítmica. Esa es la magia del método.

Abrir artículo

Arcana

Explorador

El Martillo y la Trampa

El Mensajero y el Río de Cristal

Enunciado

1. Caso base y paso recursivo

2. Algoritmo

3. Recurrencia y Teorema Maestro

4. ¿Es una mejora respecto a la búsqueda lineal?

El Archivo Roto del Archiduque

Enunciado

La Profecía de los Mercaderes

Enunciado: Máxima Ganancia por Subarray

El Contador de Traidores

Enunciado: Contar Inversiones

La Torre de los Ecos Infinitos y el Engaño del Oráculo

Enunciado: Fibonacci Recursivo Ingenuo

1. ¿Es esto realmente división y conquista?

2. Complejidad

3. Solución correcta: $O (n)$

4. División y conquista vs. programación dinámica

El Torneo de las Casas Gemelas

Enunciado: Multiplicación de Polinomios / Introducción a FFT

Vista Gráfica

Retroenlaces

Método	Complejidad	Paradigma
Multiplicación naïve	$O (n^{2})$	Fuerza bruta
Karatsuba	$O (n^{1.585})$	División y Conquista
FFT / NTT	$O (n lo g n)$	División y Conquista + matemática

Arcana

Explorador

El Martillo y la Trampa

El Mensajero y el Río de Cristal

Enunciado

1. Caso base y paso recursivo

2. Algoritmo

3. Recurrencia y Teorema Maestro

4. ¿Es una mejora respecto a la búsqueda lineal?

El Archivo Roto del Archiduque

Enunciado

La Profecía de los Mercaderes

Enunciado: Máxima Ganancia por Subarray

El Contador de Traidores

Enunciado: Contar Inversiones

La Torre de los Ecos Infinitos y el Engaño del Oráculo

Enunciado: Fibonacci Recursivo Ingenuo

1. ¿Es esto realmente división y conquista?

2. Complejidad

3. Solución correcta: O(n)

4. División y conquista vs. programación dinámica

El Torneo de las Casas Gemelas

Enunciado: Multiplicación de Polinomios / Introducción a FFT

Vista Gráfica

Retroenlaces

3. Solución correcta: $O (n)$