Sesión 63: CTCI Cap. 6 & LeetCode 887 — Algoritmos Minimax Extremos: Super Egg Drop y Consolidación de Semana 9#

Tiempo estimado: 75-85 minutos. Nivel: De Junior/Trainee a Staff Specialist. Herramientas obligatorias: Hoja cuadriculada, lápiz, regla y calculadora.

1. Diccionario de Conceptos del Día (Desde Cero para Junior / Trainee)#

Consulta rápida: Glosario Maestro | Guía de Diagramas

Problema del Tiro de Huevos (Egg Dropping Puzzle)#

• (a) En palabras simples (intuición): Tienes un edificio de N pisos y una canasta con K huevos idénticos. Existe un piso secreto F tal que si tiras un huevo desde el piso F o más abajo, no se rompe; pero si lo tiras desde cualquier piso más arriba de F, se rompe irremisiblemente. Tu objetivo no es encontrar el piso de suerte en un solo intento, sino diseñar una estrategia infalible que garantice encontrar F con el menor número posible de tiradas en el peor de los casos.
• (b) Definición técnica paso a paso: Problema clásico de optimización minimax sobre árboles de decisión con recursos destructibles:
• Si un huevo se rompe, se pierde (K → K - 1) y solo podemos buscar en los pisos inferiores.
• Si el huevo no se rompe, se reutiliza intacto (K huevos disponibles) y solo debemos buscar en los pisos superiores.
• El piso $0$ significa que el huevo se rompe incluso desde el piso 1.
• (c) Cómo funciona en Rust (memoria y tipos): Se implementa mediante programación dinámica con un vector unidimensional en el Heap Vec<usize> de tamaño K + 1, actualizándolo en orden descendente para reutilizar el estado previo sin reservas de memoria redundantes.
• (d) Error típico de Junior: Asumir que se puede hacer búsqueda binaria pura dividiendo a la mitad (N/2); si solo tienes 1 huevo y lo tiras desde el piso 50 y se rompe, el huevo se destruyó y jamás podrás saber si el piso crítico era el 1, el 2 o el 49.

Números Triangulares y Estrategia de Paso Decreciente (K = 2)#

• (a) En palabras simples (intuición): Si tienes 2 huevos y tiras el primero cada 10 pisos (10, 20, 30...), si se rompe en el piso 100, habrás gastado 10 tiradas con el primer huevo más 9 tiradas con el segundo (pisos 91 al 99), sumando 19 tiradas. Pero si se rompía en el piso 10, solo gastabas 1 + 9 = 10 tiradas. La estrategia justa debe equilibrar ambos extremos: cada vez que el primer huevo sobrevive a un piso, tu siguiente salto debe ser 1 piso más corto (x, x-1, x-2, …, 1). Así, si el primer huevo gasta una tirada más, el segundo huevo tendrá que revisar un piso menos, logrando que la suma de tiradas sea exactamente la misma constante en el peor de los casos.
• (b) Definición técnica paso a paso: Para K=2 huevos, la suma de los primeros x enteros (número triangular) debe ser al menos N:

Resolviendo la ecuación cuadrática por la fórmula general:

Para N = 100, x = 14 intentos como máximo.

• (c) Cómo funciona en Rust (memoria y tipos): Se calcula en tiempo O(1) físico usando la función f64::sqrt() sobre conversiones de enteros n as f64.
• (d) Error típico de Junior: Intentar saltos de tamaño fijo (k = √(N) = 10), produciendo un desbalance severo en el peor caso (10 + 9 = 19 > 14).

Programación Dinámica Minimax (O(K · N²))#

• (a) En palabras simples (intuición): Imagina que juegas contra el destino, que siempre elegirá la peor suerte posible para ti. Por cada piso x donde decidas tirar el huevo, calculas: "¿cuál es el peor escenario? ¿que se rompa o que no se rompa?". Tomas el peor de los dos (max) y luego, entre todos los pisos posibles, eliges el piso x que haga ese peor escenario lo menos doloroso posible (min).
• (b) Definición técnica paso a paso: Ecuación de recurrencia clásica de Bellman:

• dp(k - 1, x - 1): El huevo se rompe; buscamos en los x - 1 pisos inferiores con k - 1 huevos.
• dp(k, n - x): El huevo no se rompe; buscamos en los n - x pisos superiores con k huevos.
• (c) Cómo funciona en Rust (memoria y tipos): Requiere una matriz bidimensional Vec<Vec<usize>> de dimensiones (K+1) × (N+1) en el Heap.
• (d) Error típico de Junior: Proponer esta solución en una entrevista para LeetCode 887 donde N = 10,000; con N² = 10⁸ iteraciones, el código recibe un veredicto de Time Limit Exceeded (TLE).

Inversión Dual de Función de Estado (O(K · M))#

• (a) En palabras simples (intuición): En lugar de preguntarte la pregunta difícil: "Dados 3 huevos y 10,000 pisos, ¿cuántos tiros necesito?", dale la vuelta al cerebro e inventa la pregunta fácil: "Si tengo 3 huevos y me permites hacer exactamente 10 tiros, ¿cuál es el edificio más alto posible en el que puedo garantizar encontrar la respuesta?". Vas aumentando los tiros de 1 en 1 (m = 1, 2, 3...) hasta que el edificio que puedes resolver sea mayor o igual a 10,000.
• (b) Definición técnica paso a paso: Transformación matemática donde los intentos M pasan de ser el valor de la función a ser una dimensión de estado:

• Si el huevo se rompe en el piso elegido, podemos cubrir con los tiros y huevos restantes dp[m - 1][k - 1] pisos hacia abajo.
• Si el huevo sobrevive, podemos cubrir dp[m - 1][k] pisos hacia arriba.
• Sumamos el piso actual donde tiramos (+1).
• La iteración se detiene en cuanto dp[m][k] ≥ N.
• (c) Cómo funciona en Rust (memoria y tipos): Solo requiere un vector 1D dp: Vec<usize> de tamaño K + 1 en el Heap. Ejecuta en menos de 2 milisegundos.
• (d) Error típico de Junior: No darse cuenta de que la recurrencia dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1 es análoga al Triángulo de Pascal y a combinaciones sum binom{m}{i}, permitiendo resolver el problema sin matrices masivas.

2. Desglose Conceptual desde Primeros Principios (Sin Asumir Nada)#

La Demostración Geométrica de las Curvas Monótonas#

Para entender por qué la búsqueda binaria acelera la DP de O(K N²) a O(K N log N):

Fijemos el número de huevos k y el número total de pisos n, y analicemos qué le sucede a las dos funciones al variar el piso de prueba x ∈ [1, n]:

1. Función del Huevo Roto:
   f(x) = dp(k - 1, x - 1)
   A medida que x aumenta de $1$ a n, el número de pisos por debajo x - 1 crece. Más pisos siempre exigen igual o mayor número de intentos. Por ende, f(x) es una función estrictamente monótona creciente.
2. Función del Huevo Intacto:
   g(x) = dp(k, n - x)
   A medida que x aumenta de $1$ a n, el número de pisos por encima n - x decrece. Menos pisos exigen igual o menor número de intentos. Por ende, g(x) es una función estrictamente monótona decreciente.

  Intentos
     ^
     |         f(x) = dp(k-1, x-1) [CRECIENTE]
     |              /
     |             /  Punto Óptimo
     |            /     Minimax
     |           /         |
     |          /          V
     |         *           X           *
     |          \         / \         /
     |           \       /   \       /
     |            \     /     \     /
     |             \   /       \   /
     |              \ /         \ /
     |               *           *
     |                \         /
     |                 \       /
     |                  \     /
     |                   \   /
     |                    \ /
     |                     *   g(x) = dp(k, n-x) [DECRECIENTE]
     +--------------------------------------------------------> Piso x
     1                     mid                                n

• Teorema del Valle Convexo: El valor max(f(x), g(x)) forma una curva en forma de "V". Su punto mínimo absoluto se encuentra en el punto de intersección f(x) ≈ g(x).
• Dado que f(x) crece y g(x) decrece, podemos localizar este piso óptimo x en tiempo logarítmico O(log n) mediante Búsqueda Binaria:
• Si f(mid) < g(mid), debemos movernos a la derecha (low = mid + 1).
• Si f(mid) > g(mid), debemos movernos a la izquierda (high = mid - 1).

3. Visualización de Arquitectura y Memoria en Rust#

Diagrama Arquitectónico de Decisión#

Consulta el diagrama vectorial:

flowchart TD
    EGG["Tirar huevo en piso X"] --> BROKE{"¿Se rompe el huevo?"}
    BROKE -->|Sí| DOWN["Buscar en pisos inferiores [1 .. X-1]<br/>Huevos restantes: k - 1<br/>Tiros restantes: m - 1"]
    BROKE -->|No| UP["Buscar en pisos superiores [X+1 .. N]<br/>Huevos restantes: k<br/>Tiros restantes: m - 1"]
    DOWN --> COMB["dp[m][k] = dp[m-1][k-1] + dp[m-1][k] + 1"]
    UP --> COMB

Visualización Cuadro por Cuadro de Memoria en Rust (Stack vs Heap)#

Evolución del vector dp: Vec<usize> de tamaño K + 1 para K = 2 huevos con la función dual óptima:

INICIALIZACIÓN:
Stack:
  k = 2, n = 6
  moves = 0
  dp: [ptr, cap: 3, len: 3]
Heap:
  dp: [0, 0, 0]  (índices 0, 1, 2)

MOVIMIENTO 1 (moves = 1):
  egg = 2: dp[2] = dp[1] + dp[2] + 1 = 0 + 0 + 1 = 1
  egg = 1: dp[1] = dp[0] + dp[1] + 1 = 0 + 0 + 1 = 1
Heap:
  dp: [0, 1, 1]  (con 1 tiro y 2 huevos cubrimos max 1 piso; 1 < 6, continúa)

MOVIMIENTO 2 (moves = 2):
  egg = 2: dp[2] = dp[1] + dp[2] + 1 = 1 + 1 + 1 = 3
  egg = 1: dp[1] = dp[0] + dp[1] + 1 = 0 + 1 + 1 = 2
Heap:
  dp: [0, 2, 3]  (con 2 tiros y 2 huevos cubrimos max 3 pisos; 3 < 6, continúa)

MOVIMIENTO 3 (moves = 3):
  egg = 2: dp[2] = dp[1] + dp[2] + 1 = 2 + 3 + 1 = 6
  egg = 1: dp[1] = dp[0] + dp[1] + 1 = 0 + 2 + 1 = 3
Heap:
  dp: [0, 3, 6]  (con 3 tiros y 2 huevos cubrimos max 6 pisos; 6 >= 6, ¡ALCANZADO!)

TERMINACIÓN:
Retorna moves = 3.
Tiempo total: 3 iteraciones de 2 pasos = 6 operaciones aritméticas elementales.

4. Implementación Canónica en Rust (Compilable con rustc --test)#

Archivo de referencia: practica-rust/dia_63.rs

/// Solución analítica para 2 huevos y N pisos en O(1) tiempo.
pub fn two_eggs_classic(n: i32) -> i32 {
    if n <= 0 {
        return 0;
    }
    let n_f64 = n as f64;
    ((-1.0 + (1.0 + 8.0 * n_f64).sqrt()) / 2.0).ceil() as i32
}

/// LeetCode 887: Inversión de función de estado en O(K * M) tiempo y O(K) espacio.
pub fn super_egg_drop_optimal(k: i32, n: i32) -> i32 {
    let k = k as usize;
    let n = n as usize;

    if n <= 1 || k <= 1 {
        return n as i32;
    }

    let mut dp = vec![0usize; k + 1];
    let mut moves = 0;

    while dp[k] < n {
        moves += 1;
        for egg in (1..=k).rev() {
            dp[egg] = dp[egg - 1] + dp[egg] + 1;
        }
    }

    moves as i32
}

/// Solución alternativa con DP y Búsqueda Binaria en O(K * N log N).
pub fn super_egg_drop_dp_bs(k: i32, n: i32) -> i32 {
    let k = k as usize;
    let n = n as usize;
    let mut dp = vec![vec![0usize; n + 1]; k + 1];

    for floor in 1..=n {
        dp[1][floor] = floor;
    }
    for egg in 1..=k {
        dp[egg][0] = 0;
        dp[egg][1] = 1;
    }

    for egg in 2..=k {
        for floor in 2..=n {
            let mut low = 1;
            let mut high = floor;
            let mut ans = floor;

            while low <= high {
                let mid = low + (high - low) / 2;
                let broken = dp[egg - 1][mid - 1];
                let not_broken = dp[egg][floor - mid];

                let worst_case = 1 + broken.max(not_broken);
                ans = ans.min(worst_case);

                if broken == not_broken {
                    break;
                } else if broken < not_broken {
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            dp[egg][floor] = ans;
        }
    }

    dp[k][n] as i32
}

Implementación de Referencia en Python Tipado#

from typing import List


def super_egg_drop_optimal_py(k: int, n: int) -> int:
    """LeetCode 887 con inversión dual de estado en O(K * M) tiempo y O(K) espacio."""
    dp = [0] * (k + 1)
    moves = 0
    while dp[k] < n:
        moves += 1
        for egg in range(k, 0, -1):
            dp[egg] = dp[egg - 1] + dp[egg] + 1
    return moves


def two_eggs_classic_py(n: int) -> int:
    """CTCI Cap. 6 en O(1) tiempo usando la fórmula cuadrática de números triangulares."""
    import math

    if n <= 0:
        return 0
    return math.ceil((-1 + math.sqrt(1 + 8 * n)) / 2)

5. Preguntas de Comprensión Profunda y Diagnóstico Socrático#

6. Navegación#

• ← Sesión 62: CTCI Cap. 9 — Consistent Hashing y Token Bucket
• Sesión 64: Test Diagnóstico 1 — DP Avanzada y Backtracking con Expresiones Regulares →
• Mapa del Curso
• Glosario Maestro
• Guía de Diagramas de Arquitectura