Segunda batería de entrenamiento: diseño. Aquí ejercitamos las cuatro estrategias del Módulo 3 —divide y vencerás (03-01), greedy (03-02), programación dinámica (03-03) y backtracking (03-04)— sobre problemas nuevos de RutaBus, distintos de los que resolvimos en el curso. Los clásicos del Módulo 4 te servirán de referencia (verás que más de uno reaparece disfrazado).

Cómo trabajar esta lección: en diseño, mirar la solución antes de tiempo es especialmente dañino, porque el valor del ejercicio está en el rato de exploración: probar un enfoque, ver que falla, cambiar. Dedica a cada problema al menos 20–30 minutos con papel y editor antes de leer la solución. Y cuando la leas, no te limites a validar el código: compara tu razonamiento con el razonamiento expuesto.

1. Divide y vencerás: medir el desorden de las llegadas.
2. Greedy: refuerzos en franjas de saturación (con justificación) y bonos de transbordo (con contraejemplo).
3. Programación dinámica: la tarifa óptima del inspector, con tabla y reconstrucción.
4. Backtracking con poda: comités de revisión de líneas.
5. Diagnóstico: tres mini-problemas, ¿qué estrategia encaja en cada uno?

Dificultad: media

Los autobuses de L1 salen de cochera en orden: el bus 0 primero, luego el 1, etc. La lista llegadas contiene el instante (en minutos) en que cada bus llegó a Estación Norte: llegadas[i] es la llegada del bus que salió en posición i. Un adelantamiento es un par i < j tal que llegadas[i] > llegadas[j] (un bus que salió antes llegó después). El número de adelantamientos mide el "desorden" de la línea y se usa como indicador de calidad.

Escribe contar_adelantamientos(llegadas) en Θ(n log n) usando divide y vencerás. La versión de fuerza bruta (comparar todos los pares) es Θ(n²), como ya sabes por el ejercicio 1 de 06-01.

Pista: es exactamente la estructura de merge_sort (04-03). Pregúntate qué información sobre pares cruzados puedes obtener gratis en el momento de la mezcla, cuando ambas mitades ya están ordenadas.

La clave de divide y vencerás (03-01) es encontrar la descomposición: los adelantamientos son de tres tipos — ambos índices en la mitad izquierda, ambos en la derecha, o cruzados (i en la izquierda, j en la derecha). Los dos primeros los resuelve la recursión. Los cruzados serían Θ(n²) de contar a lo bruto... salvo que las mitades estén ordenadas: entonces, durante la mezcla de merge (04-03), cada vez que tomamos un elemento de la mitad derecha antes que uno de la izquierda, ese elemento derecho es menor que todos los que quedan en la izquierda, y cada uno de ellos forma un adelantamiento con él.

Por qué funciona: cuando der[j] < izq[i], como izq está ordenada, der[j] también es menor que izq[i+1], ..., izq[-1]. Son len(izq) - i adelantamientos contados de golpe, en O(1). Ningún par se cuenta dos veces (cada par cruzado se detecta exactamente cuando su elemento derecho sale de la mezcla) y ninguno se escapa.

Complejidad: la recurrencia es la misma de merge_sort, T(n) = 2T(n/2) + Θ(n), que ya resolvimos en 04-03: Θ(n log n). El espacio auxiliar es Θ(n) por las listas de mezcla.

Errores típicos: (1) contar solo pares adyacentes desordenados — un vector puede tener 1 desorden adyacente y n²/4 adelantamientos totales; (2) sumar len(izq) - i en la rama equivocada (cuando sale el izquierdo no hay adelantamiento); (3) contar y no devolver la lista ordenada, con lo que las mitades nunca están ordenadas y la cuenta de cruzados es incorrecta.

Dificultad: media

Dos problemas independientes; en uno greedy es correcto y hay que justificarlo, en el otro es incorrecto y hay que dar un contraejemplo. Parte de que no sabes cuál es cuál.

Parte A — Franjas de refuerzo. El sistema de monitorización produce la lista ordenada de minutos del día en que L2 estuvo saturada, p. ej. criticos = [485, 490, 510, 545, 700, 715] (minutos desde medianoche). Un bus de refuerzo cubre exactamente 30 minutos desde su hora de incorporación: si se incorpora en el minuto t, cubre [t, t+30]. Diseña un algoritmo que calcule el mínimo número de refuerzos (y sus horas) para que todo minuto crítico quede cubierto.

Parte B — Bonos de transbordo. Un usuario hará exactamente 8 viajes este mes. Tarifas: billete sencillo 2,00 €; bono de 5 viajes 6,00 € (1,20 €/viaje); bono de 8 viajes 10,40 € (1,30 €/viaje). Un compañero propone este greedy: "compra siempre el título con menor precio por viaje de entre los que no superen los viajes restantes; completa con sencillos". ¿Es correcto? Justifícalo o refútalo.

Parte A — greedy correcto. Estrategia: recorre los minutos críticos en orden; cuando encuentres uno no cubierto, incorpora un refuerzo exactamente en ese minuto (lo más tarde posible que aún lo cubre), y salta todos los críticos que caen en su ventana.

Justificación (argumento de intercambio, como en 03-02): sea m₁ el primer minuto crítico. Toda solución válida tiene algún bus con inicio t ≤ m₁ (alguien debe cubrir m₁). Si en esa solución sustituimos ese bus por uno que empieza exactamente en m₁, su ventana [m₁, m₁+30] cubre todo lo que cubría [t, t+30] dentro de los críticos (no hay críticos antes de m₁, y la ventana se desplaza hacia la derecha, donde están los demás). La solución sigue siendo válida y del mismo tamaño. Repitiendo el argumento con el siguiente crítico no cubierto, cualquier solución óptima se transforma en la greedy sin añadir buses: la greedy es óptima. Coste: Θ(n) si la lista viene ordenada (Θ(n log n) si hay que ordenarla).

Parte B — greedy incorrecto. Seguimos la regla con 8 viajes: el menor precio por viaje es el bono de 5 (1,20 €). Lo compramos (quedan 3 viajes); ni el bono de 5 ni el de 8 "caben" en 3 viajes restantes, así que completamos con 3 sencillos.

Contraejemplo encontrado: el greedy paga 12,00 € cuando el óptimo cuesta 10,40 €. El fallo es el de siempre (recuerda cambio_greedy en 03-02): el criterio local "mejor precio por viaje" no ve que fraccionar la compra obliga a completar con el título más caro. Este problema tiene subestructura óptima y decisiones que se solapan: es terreno de programación dinámica, que es justo lo que hacemos en el siguiente ejercicio.

Error típico: "probé el greedy con dos ejemplos y funcionó, luego es correcto". Greedy exige demostración (intercambio) o contraejemplo; los ejemplos favorables no demuestran nada.

Dificultad: alta

Un inspector de RutaBus debe desplazarse los días dias = [1, 2, 4, 5, 6, 9, 10, 11, 12, 20, 21] del mes. Tarifas: billete de día 2 € (cubre 1 día), abono semanal 9 € (cubre 7 días consecutivos), abono mensual 28 € (cubre 30 días consecutivos). Diseña con programación dinámica (tabulación, como coste_minimo en 03-03) un algoritmo que calcule el coste mínimo para cubrir todos los días de viaje, y reconstruye qué títulos comprar y qué día. Da la definición del subproblema, la recurrencia, la tabla y la complejidad.

Pista: define el subproblema por día del calendario, no por índice de la lista de viajes: "coste mínimo para cubrir todos los días de viaje hasta el día d".

Subproblema: dp[d] = coste mínimo para cubrir todos los días de viaje ≤ d, con d de 0 al último día de viaje.

Recurrencia: si el día d no se viaja, no hay que comprar nada nuevo: dp[d] = dp[d-1]. Si se viaja, hay tres decisiones posibles, y nos quedamos con la más barata:

• billete de día: dp[d-1] + 2
• abono semanal que termine en d (cubre d−6..d): dp[max(0, d-7)] + 9
• abono mensual que termine en d: dp[max(0, d-30)] + 28

Traza de la tabla (solo los días interesantes):

Resultado: 21 € — un abono semanal que cubre los días 1–7 (9 €) más seis billetes de día (9, 10, 11, 12, 20, 21). Compáralo con las alternativas ingenuas: 11 billetes sueltos = 22 €, abono mensual = 28 €. (En los días 10–12 hay empates: cuatro billetes tras el semanal cuestan lo mismo que otras combinaciones; la tabla se queda con la primera opción mínima.)

Complejidad: Θ(D · 3) = Θ(D) en tiempo y Θ(D) en espacio, con D el último día (aquí 21). Fíjate en que depende del calendario, no del número de viajes.

Errores típicos: (1) plantear el greedy "compra el abono si hay ≥ 5 viajes en la semana" — falla en configuraciones límite, como demostró el ejercicio 2B; (2) olvidar el max(0, d - dur) y acceder a índices negativos (que en Python no dan error: ¡leen por el final de la lista y corrompen el resultado en silencio!); (3) guardar solo el coste y no la elección, con lo que la reconstrucción —que es lo que la app necesita mostrar al usuario— es imposible, como insistimos con mochila_mejoras en 03-03.

Dificultad: alta

Auditoría interna exige formar un comité de revisión de 2 personas por cada línea (L1, L2, L3). Revisores disponibles: Ana, Bruno, Carla, Diego y Elena. Restricciones:

1. Nadie puede revisar la línea en la que conduce: Ana conduce L1; Bruno y Carla conducen L2; Diego conduce L3.
2. Cada revisor puede participar como máximo en 2 comités.
3. Elena y Diego tienen turnos incompatibles: no pueden coincidir en el mismo comité.

Escribe formar_comites() con backtracking (03-04) que devuelva una asignación válida (o None), e incluye al menos una poda que corte ramas sin futuro antes de explorarlas.

Espacio de estados: para cada línea, elegir un par de revisores. Sin restricciones habría C(5,2)³ = 10³ = 1000 combinaciones; las restricciones y la poda lo reducen drásticamente.

Razonamiento: el esqueleto es el patrón decidir → recursión → deshacer de 03-04 (idéntico en espíritu a asignar_turnos). La comprobación valido es la poda por restricciones: descarta el par antes de bajar un nivel. La poda de capacidad es más interesante: si quedan 2 líneas por cubrir (4 plazas) pero entre todos los revisores solo queda capacidad para 3 participaciones, ninguna combinación futura puede funcionar — cortamos sin enumerar los ~100 nodos de ese subárbol. Es el mismo principio que la poda de N-Reinas: detectar la imposibilidad lo antes posible.

Una solución válida que encuentra el algoritmo: L1 = {Bruno, Carla} (ambos conducen L2, pueden revisar L1), L2 = {Ana, Diego}, L3 = {Ana, Bruno} — Ana y Bruno quedan con 2 comités (límite justo), Diego no coincide con Elena en ningún comité, y nadie revisa su propia línea.

Complejidad: el peor caso teórico sigue siendo exponencial en el número de líneas — O(C(r,2)^L) —, como todo backtracking; las podas no cambian el peor caso, cambian el caso real. Por eso en 03-04 insistimos: backtracking sin poda es fuerza bruta con otro nombre.

Errores típicos: (1) olvidar deshacer uso[r] -= 1 al retroceder — el estado queda corrupto y el algoritmo declara imposibles casos que tienen solución; (2) validar la asignación completa solo al final (en i == len(LINEAS)) en lugar de podar en cada nivel: correcto pero exponencialmente más lento; (3) mutar asignacion y devolverla sin copiar, con lo que el del posterior puede vaciar el resultado.

Dificultad: media

Para cada mini-problema, decide qué estrategia de diseño usarías (divide y vencerás, greedy, programación dinámica o backtracking) y justifica en 3–5 líneas por qué, apoyándote en la tabla comparativa del final de 03-04. No hay que implementar nada: este ejercicio entrena el diagnóstico, que en la práctica profesional es la parte difícil.

A) RutaBus tiene 6 vehículos de reserva para repartir entre L1, L2 y L3. Una tabla empírica dice cuántos pasajeros extra capta cada línea según cuántos vehículos reciba (los rendimientos no son proporcionales: en L1, 1 vehículo aporta 300 pasajeros pero 2 aportan solo 380; en L3, 1 aporta 100 y 3 aportan 900). Hay que repartir los 6 vehículos maximizando el total de pasajeros extra.

B) El departamento comercial tiene n solicitudes de publicidad en la marquesina de Plaza Mayor, cada una con fecha de inicio y fin, todas pagan lo mismo. Hay que aceptar el máximo número de solicitudes sin que se solapen.

C) Hay que planificar la visita trimestral del auditor a 8 paradas concretas, respetando precedencias ("Hospital Central antes que Parque del Río") y ventanas horarias por parada, y hay que listar todas las planificaciones válidas para que dirección elija.

A) Programación dinámica. Señales: decisiones secuenciales (cuántos vehículos doy a cada línea), un recurso acotado que se consume (los 6 vehículos: es el "peso" de una mochila), subestructura óptima (el mejor reparto entre L2 y L3 de lo que sobre no depende de cómo usé lo asignado a L1, solo de cuánto) y subproblemas solapados (muchos caminos llevan a "quedan 3 vehículos para 2 líneas"). Greedy incremental ("da cada vehículo a la línea que más mejora") falla precisamente porque los rendimientos no son cóncavos: en L3 el tercer vehículo aporta más que el primero, y el greedy nunca llega a verlo. Es la mochila de mochila_mejoras (03-03) con disfraz de reparto.

B) Greedy. Es la selección de actividades (03-02, asignar_trayectos): intervalos, todos de igual valor, maximizar cuántos caben sin solaparse. El criterio "acepta siempre la solicitud que termina antes de entre las compatibles" tiene demostración de optimalidad por intercambio. No hace falta PD (no hay pesos ni valores distintos que obliguen a comparar combinaciones) ni backtracking (no queremos todas las soluciones, solo una óptima, y greedy la encuentra en Θ(n log n)).

C) Backtracking. Señales inequívocas: restricciones combinadas (precedencias + ventanas), y sobre todo el requisito de enumerar todas las soluciones válidas — greedy y PD producen una solución (óptima), no un catálogo. El espacio de estados son las permutaciones de 8 paradas (8! = 40 320), inabordable con fuerza bruta pura si crece, pero muy podable: en cuanto una planificación parcial viola una precedencia o una ventana, se corta la rama entera, como en rutas_inspeccion (03-04).

Error típico en diagnóstico: elegir estrategia por el dominio del problema ("es de intervalos, luego greedy") en lugar de por sus propiedades (¿elección local segura? ¿subproblemas solapados? ¿hay que enumerar?). B es greedy y A es PD, y ambos podrían describirse como "repartir recursos": lo que decide es la estructura, no el enunciado.

Has diseñado desde cero con las cuatro estrategias: divide y vencerás aprovechando la mezcla de merge_sort para contar adelantamientos en Θ(n log n); greedy con las dos caras que siempre tiene —demostración por intercambio cuando funciona, contraejemplo cuando no—; programación dinámica con subproblema, recurrencia, tabla y reconstrucción para las tarifas del inspector; y backtracking con podas de restricción y de capacidad para los comités. Y, quizá lo más importante, has practicado el diagnóstico: mirar un problema nuevo y reconocer qué estrategia pide, que es la habilidad que de verdad se usa en el trabajo diario.

Con el análisis (06-01) y el diseño (esta lección) entrenados, queda el tercer músculo del curso: en la siguiente lección practicaremos la optimización — coger código RutaBus lento y realista y aplicarle, con disciplina, el método del Módulo 5.