División y Conquista

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.

1. 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 Oráculo. La recurrencia que encontrarás es T(n) = 2·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)?

   Enlace al original

2. 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 un método llamado Merge Sort: “divide la pila en dos, ordena cada mitad, y luego combínalas”. 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 Maestro. 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?

   Enlace al original

3. 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.

   Semilla del Oráculo 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·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?

   Enlace al original

4. 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\log n)$, no en $O(n^2)$.

   Pista clave: 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.

   Enlace al original

5. La Torre Fibonacci y el Engaño del Oráculo

   En la 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ⁿ).
   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.

   Enlace al original

6. 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\log 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·T(n/2) + O(n). Aplica el Teorema Maestro y obtén O(n^log₂3) ≈ 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\log 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²)	Fuerza bruta
   Karatsuba	O(n^1.585)	División y Conquista
   FFT / NTT	O(n log 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.

   Enlace al original