Herramientas de usuario
brainstorm:brainstorm-algoritmos
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
brainstorm:brainstorm-algoritmos [2017/06/19 06:17] santo |
brainstorm:brainstorm-algoritmos [2019/09/08 17:35] (actual) santo |
||
|---|---|---|---|
| Línea 2: | Línea 2: | ||
| - | Brainstorm de ideas de temas algorítmicos para desarrollar, en forma de lista. Varios de estos temas exceden el nivel usual de la IOI / competencias de nivel secundario, siendo más avanzados y adecuados para nivel universitario, ya que esta lista se inició a partir de una ya existente lista de temas apuntada a la competencia de programación universitaria ACM-ICPC. | + | Brainstorm de ideas de temas algorítmicos para desarrollar, en forma de lista. Muchísimos de estos temas exceden el nivel usual de la IOI / competencias de nivel secundario, siendo más avanzados y adecuados para nivel universitario, ya que esta lista se inició a partir de una ya existente lista de temas apuntada a la competencia de programación universitaria ACM-ICPC. |
| - | Algunos no son necesariamente más avanzados pero están al momento de escribir estas líneas "explicitely excluded" en el Syllabus de IOI. | + | Algunos no son necesariamente más avanzados pero están al momento de escribir estas líneas "explicitly excluded" en el Syllabus de IOI. |
| No obstante, como lista ideas, con temas existentes posibles para desarrollar, no deja de ser una lista valiosa para generar material apuntado a OIA y competencias de nivel secundario. | No obstante, como lista ideas, con temas existentes posibles para desarrollar, no deja de ser una lista valiosa para generar material apuntado a OIA y competencias de nivel secundario. | ||
| Línea 19: | Línea 19: | ||
| * BFS con cola de dos puntas [Aristas 0 y 1] | * BFS con cola de dos puntas [Aristas 0 y 1] | ||
| * BFS con K+1 bolsas [aristas 0..K] | * BFS con K+1 bolsas [aristas 0..K] | ||
| + | * Truquito "ahorrar aristas": Ajedrez, Alfil | ||
| * DFS | * DFS | ||
| * Back Edges | * Back Edges | ||
| Línea 79: | Línea 80: | ||
| * Radio, centro y diámetro de un árbol en tiempo lineal. | * Radio, centro y diámetro de un árbol en tiempo lineal. | ||
| * Centroid decomposition | * Centroid decomposition | ||
| + | * Prufer codes | ||
| * Grafos planares | * Grafos planares | ||
| * Fórmula de Euler | * Fórmula de Euler | ||
| Línea 102: | Línea 104: | ||
| * Estructuras de datos | * Estructuras de datos | ||
| * Arreglos | * Arreglos | ||
| + | * "Truco del arreglo autolimpiante" | ||
| * STL (set, multiset, map, multimap, vector, queue, stack, deque, priority_queue, list, etc) | * STL (set, multiset, map, multimap, vector, queue, stack, deque, priority_queue, list, etc) | ||
| * Listas enlazadas | * Listas enlazadas | ||
| Línea 111: | Línea 114: | ||
| * Heap (para priority queue), heapsort, heapify en O(N) | * Heap (para priority queue), heapsort, heapify en O(N) | ||
| * Union Find (Implementacion con listas y con arbol, la de listas es facil de codear y permite iterar las componentes, se aplica al problema Hackers de la local de UBA 2010) | * Union Find (Implementacion con listas y con arbol, la de listas es facil de codear y permite iterar las componentes, se aplica al problema Hackers de la local de UBA 2010) | ||
| - | * RMQ (Segment tree sobre arreglo) (Multi Dimension) | + | * RMQ (Segment tree sobre arreglo) (Updates con recalculo vs acumulativos) (Multi Dimension) |
| * Sliding Windows, Sliding-RMQ (para en O(N) calcular el RMQ de subarreglos de un tamaño K dado) | * Sliding Windows, Sliding-RMQ (para en O(N) calcular el RMQ de subarreglos de un tamaño K dado) | ||
| - | * "La DP de Huguito" | + | * Variante de sliding window RMQ con dos 2deque para guardar los dos mejores |
| + | * "La DP de Huguito" (anda para cualquier operador asociativo, eso incluye "guardar los mejores k") | ||
| * "Estructura de los saltitos potencia de 2" en árbol con raíz | * "Estructura de los saltitos potencia de 2" en árbol con raíz | ||
| * LCA en O(lg n) u O(1) (Usando reduccion a RMQ, o usando la estructura de los saltitos). Aplicación para calcular distancias en un árbol en O(lg n) | * LCA en O(lg n) u O(1) (Usando reduccion a RMQ, o usando la estructura de los saltitos). Aplicación para calcular distancias en un árbol en O(lg n) | ||
| Línea 126: | Línea 130: | ||
| * Aho-Corasick. | * Aho-Corasick. | ||
| * Suffix Array (Algoritmo de Larsson y Sadakane), LCP | * Suffix Array (Algoritmo de Larsson y Sadakane), LCP | ||
| + | * BWT (Mismo algoritmo Suffix Array) / BWT inversa en O(N) | ||
| + | * Compresión de coordenadas | ||
| * Programacion Dinamica | * Programacion Dinamica | ||
| * Maxima subsecuencia creciente (En O(n^2), y su variante en O(n lg n)) | * Maxima subsecuencia creciente (En O(n^2), y su variante en O(n lg n)) | ||
| Línea 140: | Línea 146: | ||
| * Dinámicas con máscaras de bits: TSP y muchas otras. | * Dinámicas con máscaras de bits: TSP y muchas otras. | ||
| * Dinámicas con "frente": Poner fichitas / tubitos en un tablero, y muchas otras | * Dinámicas con "frente": Poner fichitas / tubitos en un tablero, y muchas otras | ||
| - | * DP Optimization Tricks http://codeforces.com/blog/entry/8219 | + | * DP Optimization Tricks (Chull Trick, Knuth, Divide and Conquer Optimization) http://codeforces.com/blog/entry/8219 |
| * Josephus problem en K * ln N | * Josephus problem en K * ln N | ||
| * Matemática y afines | * Matemática y afines | ||
| Línea 164: | Línea 170: | ||
| * Chequear si un punto esta en un poligono / en un segmento / en una recta / en un plano | * Chequear si un punto esta en un poligono / en un segmento / en una recta / en un plano | ||
| * Teorema de Pick | * Teorema de Pick | ||
| + | * Triangulación de polígono (árbol de triángulos, demuestra que piso(n/3) guardias bastan) | ||
| * Par de puntos mas cercano en O(n lg n) | * Par de puntos mas cercano en O(n lg n) | ||
| + | * Truquito de que v --> (w*v, w^v) es rotohomotecia de razon ||w|| que rota llevando w al eje x positivo (permite "restar angulos en enteros", demuestra que un angulo es posible entre puntos enteros si y solo si su tangente es racional). | ||
| * Capsula convexa en O(n lg n) | * Capsula convexa en O(n lg n) | ||
| * Ancho (mínimo) de conjunto (rotating calipers en la chull) | * Ancho (mínimo) de conjunto (rotating calipers en la chull) | ||
| Línea 171: | Línea 179: | ||
| * Distancia entre dos segmentos | * Distancia entre dos segmentos | ||
| * Sweep Line (Es muy importante la idea de sweep line / sweep circle / sweep sarasa) | * Sweep Line (Es muy importante la idea de sweep line / sweep circle / sweep sarasa) | ||
| + | * Dualidad punto - línea (a,b) <--> ax + b | ||
| + | * Idea de eliminación de dominados / Convex hull trick | ||
| + | * Dualidad intervalo - punto ([A,B] -- (A,B) , complementar intervalos es reflejar por y=x (caso circular)) | ||
| + | * Truquito de la f lineal que transforma norma 1 en norma infinito (en 2D es "rotar 45") | ||
| + | * Hay O(NM) rectángulos maximales en una grilla de NxM (Implica O(T^2) para T obstáculos), y cómo enumerarlos (desde cada casilla tirar un rayito para abajo, y de donde pega, expandir para los costados. Eso pasa por todos los maximales y por algunos no maximales [y posiblemente varias veces]) | ||
| * Divide and conquer | * Divide and conquer | ||
| * Par de puntos mas cercano en O(n lg n) | * Par de puntos mas cercano en O(n lg n) | ||
| Línea 176: | Línea 189: | ||
| * Karatsuba | * Karatsuba | ||
| * Armado de fixtures (aunque hay una alternativa constructiva muy elegante y simple) | * Armado de fixtures (aunque hay una alternativa constructiva muy elegante y simple) | ||
| + | * Elemento mayoría (y solución lineal, con O(1) memoria, o alternativamente con 3/2N comparaciones) | ||
| * Meet in the middle | * Meet in the middle | ||
| * BFS (tipo cubo de Rubik) | * BFS (tipo cubo de Rubik) | ||
| Línea 191: | Línea 205: | ||
| * Problemas NP Completos: Maximum independent set, Minimum dominating set, subset sum, etc. | * Problemas NP Completos: Maximum independent set, Minimum dominating set, subset sum, etc. | ||
| * Recursiones y podas de backtracking que mejoran la complejidad (Ejemplo, Max. Ind. Subset en 1.47^N) | * Recursiones y podas de backtracking que mejoran la complejidad (Ejemplo, Max. Ind. Subset en 1.47^N) | ||
| + | * Board hashes (transposition tables, también re útil para BFS/Dijkstra) | ||
| * Teoría de juegos | * Teoría de juegos | ||
| * Cálculo con DP de posiciones ganadoras y perdedoras. Propiedad Universal. | * Cálculo con DP de posiciones ganadoras y perdedoras. Propiedad Universal. | ||
| Línea 204: | Línea 219: | ||
| * Autómatas de KMP y Aho-Corasick | * Autómatas de KMP y Aho-Corasick | ||
| * Parsing Recursivo Descendente predictivo (con "prediccion artesanal") | * Parsing Recursivo Descendente predictivo (con "prediccion artesanal") | ||
| + | * Popurrí | ||
| + | * Detección de ciclo en función (Tortuga de Floyd, Brent) | ||
| + | |||
| + | |||
brainstorm/brainstorm-algoritmos.1497853053.txt.gz · Última modificación: 2017/06/19 06:17 por santo
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
