Algoritmos y programación competitiva
Complejidad con contadores, búsqueda binaria, two pointers, sumas prefijas, merge y quick sort, backtracking, BFS, DFS, Dijkstra, programación dinámica y greedy, con el formato de la OIA y la ICPC.
15 aulas · 14 horas de práctica · en el navegador, sin instalar nada
Temario
- Complejidad medida con contadores — Antes de mandar un programa a una competencia hay que saber si entra en el tiempo. Acá se mide como lo estiman los que compiten: contando operaciones, y viendo cómo crece la cuenta cuando crece la entrada.
- Búsqueda binaria — Encontrar algo en una lista ordenada de un millón mirando veinte lugares: partir el rango a la mitad cada vez. Y la misma idea para buscar la respuesta de un problema, cuando "sirve" y "no sirve" están separados por una línea.
- Two pointers y ventana deslizante — Dos índices que se mueven sin volver atrás convierten un doble loop en uno solo: el par que suma justo, la mejor racha de k días, el tramo más corto que alcanza. Cada uno, O(n).
- Sumas prefijas — Preparar una vez, contestar al instante: con las sumas acumuladas, la suma de cualquier rango es una resta. Y la misma idea al revés para sumar a muchos rangos sin recorrerlos.
- Merge sort — Ordenar partiendo: dos mitades ordenadas se mezclan en O(n), y partir a la mitad da log n niveles. O(n log n) siempre, estable, y de yapa cuenta cuántos pares están al revés.
- Quick sort — Elegir un pivote, poner los menores a un lado y los mayores al otro, y repetir. Rapidísimo en promedio y en el lugar, pero con un peor caso cuadrático que se ve en la pista, y que se arregla eligiendo mejor el pivote.
- Backtracking: las N reinas — Probar todas las posibilidades sin escribirlas a mano: elegir, explorar y deshacer. Las combinaciones de un candado, los billetes que suman justo, y las N reinas, con la poda que corta lo que ya no puede salir.
- BFS: el camino más corto — Recorrer por capas, como una onda en el agua: primero todo lo que está a un paso, después a dos. Con una cola, el primero que llega a cada casilla llega por el camino más corto, y siguiendo de dónde vino cada uno se reconstruye el camino.
- DFS: contar islas — Ir lo más hondo posible antes de volver: el recorrido en profundidad. Pintar una mancha, hundir cada barco del mapa para contarlos, y qué hacer cuando el mapa es tan grande que la recursión no da más.
- Dijkstra — Cuando cada calle tarda distinto, contar pasos no alcanza. Dijkstra cierra los barrios de a uno, siempre el más cercano, con una cola de prioridad: la distancia de cada barrio, el orden en que se cierran y el camino, dibujados en el mapa.
- Programación dinámica I — Si un problema se arma con respuestas de problemas más chicos que se repiten, se calcula cada una una sola vez y se guarda. De a un paso: Fibonacci con memoria, la escalera de abajo hacia arriba, el combustible mínimo del cohete y el plan de vuelo.
- Programación dinámica II: la mochila — El problema más famoso de la programación dinámica: qué llevarse para que valga lo más posible sin pasarse de peso. Una tabla de dos dimensiones, cómo saber qué se eligió, la versión de una sola fila y el reparto en partes iguales.
- Greedy — Elegir siempre lo que parece mejor ahora, sin mirar atrás. A veces es la respuesta perfecta y la más rápida (el vuelto, las charlas, la fila del banco), y a veces se equivoca: saber cuál es cuál es la mitad del trabajo.
- Taller: simulacro de competencia — Cinco problemas, como en una competencia de verdad: leer bien la entrada, y en cada uno elegir el algoritmo justo. Cada respuesta es una pista del robo del trofeo de la olimpíada, y la rueda de sospechosos se va achicando hasta que queda uno.
- Taller: el GPS del colectivo — La red de colectivos de la ciudad, leída de la entrada con los nombres de las paradas. El camino con menos paradas, el más rápido, el desvío por una calle cortada, la parada obligatoria y muchas consultas: un GPS de verdad, dibujado en el mapa.