comp-prog-argentina

Temario

Lista de temas para IOI/ICPC

Existen otros temarios. Por ejemplo:

• Temario oficial de IOI
• https://youkn0wwho.academy/topic-list

Podes contribuir a este temario sugiriendo cambios en https://github.com/SebastianMestre/comp-prog-argentina/blob/trunk/raw/temario.tsv

Razonamiento formal

• Modelado y formalización de problemas
• Razonamiento ecuacional sobre programas
• Razonamiento axiomático sobre programas (lógica de Hoare)

Técnicas de resolución

• Generalización y reducción
• Invariantes
• Monotonía
• Análisis de elementos especiales (e.g. analizar máximos y mínimos)
• Coloreos (e.g. cubrir un tablero de ajedrez sin esquinas con piezas de dominó)
• Principio del palomar (e.g. mayor hueco de menor a mayor en O(N))
• Inversión del problema ("mirar para atras", e.g. perros de OIA 2019)
• Separación en componentes independientes

Grafos

Basico

• Nociones elementales y definiciones de teoria de grafos

Caminos especiales

• Circuito euleriano, teorema de existencia <=>, algoritmos para construirlo
• Circuito hamiltoniano, teoremas de Ore / Dirac

Representaciones

• Matriz de Adyacencia
• Matriz de Incidencia
• Listas de Adyacencia
• Lista de incidencia
• Grafo Implícito

BFS

• Algoritmo basico.
• BFS con cola de dos puntas [Aristas 0 y 1]
• BFS con K+1 bolsas [aristas 0..K]

DFS

• Implementacion con stack
• Implementacion recursiva
• Clasificacion de aristas en grafo no-dirigido ({tree,back}-edges)
• Clasificacion de aristas en grafo dirigido ({tree,back,forward,cross}-edges)
• Ordenamiento Topologico
• Clausura transitiva
• Componentes Fuertemente Conexas
• Deteccion de puntos de articulacion y puentes
• Componentes Biconexas
• Block-cut tree

Caminos minimos

• Dijkstra en N^2
• Dijkstra en (N + M) log N
• Distancia Min-Max (Prim)
• Bellman-Ford y su implementacion tipica.
• Bellman-Ford como programacion dinamica.
• Bellman-Ford para contar caminos entre pares de nodos.
• Bellman-Ford, deteccion y tratamiento de ciclos negativos
• Floyd-Warshall Vision como programacion dinamica.
• Floyd-Warshall y su implementacion tipica.
• Floyd-Warshall, para contar caminos entre pares de nodos.
• Floyd-Warshall como producto de matrices de adyacencia / Potencias de la matriz de adyacencia.
• Floyd-Warshall, eteccion y tratamiento de ciclos negativos
• Reconstruir caminos
• Reconstruir caminos

Arbol recubridor minimo

• Kruskal
• Relación del Minimum Spanning Tree con la distancia Min-Max.
• Aplicación a calcular la distancia min-max todos contra todos en N^2
• Solución alternativa para el mismo problema: hacerlo en el mismo Kruskal que calcula el MST

Flujo y derivados

• Algoritmo de Khun -- Matching Maximo Bipartito O(VE)
• Modelado de problemas con flujo maximo
• Modelado de problemas con corte minimo, dualidad con flujo maximo
• Algoritmo de Edmonds-Karp
• Algoritmo de Dinitz
• Algoritmos de Preflow-Push
• Manejo de la red residual de un grafo.
• Teoremas de König, Hall y Menger.
• Mínimo Cubrimiento por Caminos. Mínima Partición en Caminos. Teorema de Dilworth
• Min-cost max-flow
• min vertex cover / max independent set en grafo bipartito

Árboles

• Detección, recorrido.
• Representación de arbol con raiz: Padre de cada nodo
• Representación de arbol con raiz: Lista de adyacencia del dirigido "bajando desde la raíz".
• Radio, centro y diámetro de un árbol en tiempo lineal.

Grafos planares

• Fórmula de Euler
• Los grafos planares son ralos
• Max-clique en grafo planar
• Grafo dual
• Construir Grafo dual de un grafo planar (dado el embedding)

Complejidad computacional

• Entendimiento de la notacion asintotica (La O grande de "O(N)")
• Analisis amortizado de complejidad
• Nocion de P, NP, NP completo, algoritmo polinomial, etc
• Problemas NP completos conocidos (Camino hamiltoniano, TSP, Maximum independent set, Minimum dominating set, subset sum, etc.)
• Problemas que no se sabe que sean P ni NP completo (Factorización entera, logaritmo discreto, isomorfismo de grafos)

Ordenamiento

• Busqueda lineal
• Busqueda binaria (con LA RECETA)
• Counting Sort
• MergeSort
• QuickSort
• Mediana (o elemento iesimo) en tiempo lineal esperado (n\_th element)
• HeapSort
• BubbleSort
• InsertionSort
• RadixSort

Estructuras de datos

Básicas

• Arreglos
• Listas enlazadas
• Colas
• Pilas

C++

• STL (set, multiset, map, multimap, vector, queue, stack, deque, priority\_queue, list, etc)
• Policy based data structures de GCC (en especial indexed\_set)

Árboles

• Árboles con raíz generales
• Árbol binario de búsqueda (ABB)
• ABB balanceado (por ej, Treap)
• Heap (para priority queue), heapsort, heapify en O(N)
• Tries

Consultas sobre arreglos

• Tablas Aditivas (prefix sums)
• Binary Index Tree (Fenwick Tree)
• Union Find (Implementacion con listas y con arbol)
• RMQ (Segment tree sobre arreglo)
• Sliding Windows, Sliding-RMQ (para en O(N) calcular el RMQ de subarreglos de un tamaño K dado)
• RMQ/Fenwick 2D

Consultas sobre árboles

• Binary lifting en árbol con raíz
• LCA en O(lg n) mediante Euler Tour + RMQ
• LCA en O(lg n) mediante binary lifting
• Distancias en un arbol en O(log N) con LCA
• Heavy Light Decomposition

Varias

• Tabla hash
• Estructuras de datos persistentes (con path copying)
• Estructuras de datos para arboles dinamicos (link-cut trees)
• Principio small-to-large

Algoritmos con sqrt()

• sqrt-decomposition: Separar la secuencia del input en bloques de sqrt(N)
• Algoritmo de MO: separar queries por posicion inicial en bloques de sqrt(N)
• Combinar dos algoritmos O(nk) y O(n^2/k)
• Agrupar updates en bloques de sqrt(U), hacer queries iterando por las updates dentro de cada bloque
• Hay <= sqrt(N) elementos que aparecen >= sqrt(N) veces
• Si una suma es igual a N, hay <= sqrt(N) valores distintos

Strings

• Algoritmo KMP, y que significa su tablita.
• Z-Array
• Rabin-Karp, y uso del concepto de hash en general.
• xor-hashing y sum-hashing con una tabla de números aleatorios
• Suffix Array (Algoritmo de Larsson y Sadakane), LCP
• Matching con automatas deterministas y no deterministas (dado un automata ya hecho)
• Suffix Tree
• Suffix Automaton
• Automata de Aho-Corasick (version multicadena de KMP)
• Algoritmo de Manacher (tabla de radio de palindromos)
• Factorización de Lyndon (Mínima factorización en rotaciones mínimas)

Programacion Dinámica

• Recursion (en matematica, en programacion, recursion mutua)
• Maxima subsecuencia creciente (En O(n^2), y su variante en O(n lg n))
• Cálculo del triangulo de pascal
• Longest common subsequence
• Edit distance mínima (La común, y permitiendo swaps adyacentes)
• Producto de matrices con costo minimo
• "En una matriz yendo de una esquina a la otra solo bajando y para la derecha, maximizar la suma de las casillas visitadas."
• Knapsack (Problema de la mochila), Subset Sum
• Dar vuelto usando una cantidad minima de monedas
• Optimal Binary Search Tree en O(n^3) y O(n^2) (Knuth optimization)
• Divide and conquer optimization
• Dada una string par de {,(,[,],),} dar la minima cantidad de cambios necesarios para que sea valida.
• Dinámicas con máscaras de bits: TSP y muchas otras.
• Dinámicas con "frente": Poner fichitas / tubitos en un tablero, y muchas otras

Matemática

Analisis numérico

• Punto flotante: Conocerlos, saber que existe el error, cuentitas basicas, uso de EPSILON en los if
• Operaciones aritmeticas con enteros de longitud arbitraria

Álgebra

• Potenciacion logaritmica (binary lifting)
• Sumas de progresiones aritmeticas y geometricas con binary lifting
• Recurrencias lineales
• Sistemas de ecuaciones lineales (algoritmo de Gauss)
• Calculo de determinantes, matriz inversa (algoritmo de Gauss)
• Funciones generatrices

Combinatoria y Probabilidad

• Relacion entre combinatoria y probabilidad
• Principios de la suma y del producto
• Coeficientes binomiales / triangulo de Pascal
• Bolitas y palitos
• Inclusion-exclusion
• Linealidad de la esperanza / técnica "contribution to the sum"
• Distribución de la suma de dos variables aleatorias (convolucion)
• Convolucion rápida usando FFT
• Números de Catalan
• Cadenas de Markov
• Young Tableaux

Teoría de números

• Teorema fundamental de la aritmetica
• Aritmetica modular
• MCD (Algoritmo de euclides)
• Inverso Modular (Con euclides extendido o con pequeño teorema de Fermat)
• Teorema Chino del Resto
• Producto de matrices
• Chequeo de primalidad raiz(N)
• Criba de Eratostenes
• Chequeo de primalidad eficiente probabilistico (Miller-Rabin)
• Orden de un elemento en (N_p,*), raices primitivas
• Funcion phi de Euler
• Funciones multiplicativas, función de Mobius

Geometria

• Vectores (Suma, Resta)
• Producto escalar
• Norma, distancia euclidea (pitagoras)
• Producto vectorial
• Area de triangulos / paralelogramos, detección de sentido de giro
• Area de poligonos
• Representaciones de recta, segmento, etc estilo lineal (vectores / puntos + direccion)
• Chequear si un punto esta en un poligono / en un segmento / en una recta / en un plano
• Chequear si esta en poligono convexo en lg N
• Chequear si está en un poligono no convexo en O(N)
• Teorema de Pick
• Compresion de coordenadas
• Par de puntos mas cercano en O(n lg n)
• Capsula convexa en O(n lg n)
• Par de puntos mas lejano en O(n lg n), O(n) dada ya la capsula convexa
• Rotating calipers
• Interseccion de dos segmentos
• Distancia entre dos segmentos
• Sweep Line (Es MUY importante la idea de sweep line / sweep circle / sweep sarasa)
• Dualidad punto / linea
• Interseccion circulo - circulo y circulo - recta
• Suma de Minkowski, aplicación a distancia entre polígonos convexos
• Convex Hull Trick
• Clasificar/contar puntos dominados/dominantes

Divide and conquer

• Elemento mayoria en n lg n usando *solamente* comparaciones por igualdad entre elementos.
• Par de puntos mas cercano en O(n lg n)
• Strassen
• Karatsuba

Greedies

• Dar vuelto usando una cantidad minima de monedas
• Ordenamiento de trabajos con distintos tiempos de ejecución para minimizar el tiempo de finalización promedio.
• Optimo cubrimiento de intervalo por subintervalos.
• Codigos de Huffman
• Maxima subsecuencia creciente (resolviendo "mínima partición en subsecuencias no crecientes" + Dilworth)

Backtracking

• Fuerza Bruta
• Fuerza Bruta sobre permutaciones (next_permutation)
• Backtracking con cantidad de pasos fija (for if for if for if)
• Backtracking con cantidad de pasos variable (recursiva)
• Backtracking sobre permutaciones (recursiva)
• Backtracking sobre subconjuntos (recursiva)
• Optimización "Branch & Bound"
• Problema de las N reinas
• Cubrir un tablero con fichitas. (e.g. Codeforces 143E)
• Sudoku

Teoría de juegos

• Propiedad Universal de las posiciones P/G
• Cálculo con DP de posiciones ganadoras y perdedoras.
• Algoritmo minimax para juegos de suma cero de informacion perfecta.
• Idea de la criba para llenar tablitas como la anterior.
• Variante de la DP donde el que gana trata de ganar rápido y el que pierde de perder lento.
• Juegos combinatorios imparciales: Sumar de juegos.
• Nim. Misére Nim.
• Grundy Numbers, cálculo de los grundy numbers en tiempo lineal en el grafo, con DP. Grundy Number de una suma de juegos.

Teoría de lenguajes

• Gramatica BNF
• Autómatas Finitos
• Expresiones Regulares
• Parsing Recursivo Descendente predictivo (con "prediccion artesanal")
• Gramaticas libres de contexto

Interactivos

• Problemas estilo "descubrir el secreto"
• Problemas estilo "queries online"
• Problemas estilo "juego contra el juez"
• Heuristica de repartir parejo
• Teoria de la informacion, bits, entropia

Permutaciones

• Composicion
• Representacion de cosas como permutaciones (e.g. Rubik, o cualquier grupo)
• Transposiciones (swaps)
• Inversiones
• Contar inversiones en O(N log N) (con mergesort o con Fenwick tree)
• Ciclos
• Paridad (Mediante inversiones y mediante ciclos)

Truquitos

Estructuras de datos

• Sumas de prefijos de cadenas de paréntesis balanceadas

Grafos

• Al Reconstruir caminos, dar vuelta origen y destino (y trasponer el grafo si es dirigido) así al recorrer los padres queda el camino al derecho.

Matemática

• Gauss rápido para matrices banda: Bidiagonales, Tridiagonales, Adyacencias en una grilla rectangular.