lunes, 31 de agosto de 2009

Problemas de la semana

Queens, Knights and Pawns : Simulación
SRM 315 Div 1 Level 1 : Matemática (Invariantes)
SRM 315 Div 1 Level 2 : Backtracking

jueves, 27 de agosto de 2009

Problemas de la semana

Brownie Points : Geometría simple
HTML : Simulación
Highways : Algoritmo de Kruskal
Bitmap : BFS
Tri Tiling : DP
Invitation Cards : Algoritmo de Dijkstra aplicado al grafo dado y al grafo con aristas invertidas

miércoles, 26 de agosto de 2009

Inventario

Me parece bueno primero hacer un inventario de que sé y que me gustaría ir aprendiendo:

Que algoritmos o técnicas sé y he implementado por lo menos dos veces (en el orden que me vengan a la mente)?
  • STL (Standard Template Library) : vector, string, algorithm, queue, stack, deque, map, set
  • Programación Dinámica (DP) y memoización
  • DFS, aplicacion a test de grafo bipartito, Iterative Deepening DFS
  • BFS, 0/1 BFS (deque)
  • Algoritmos de Dijsktra (Ruta más corta)
  • Algoritmos de Floyd-Warshall (DP, ruta más corta)
  • Algoritmo de Bellman - Ford (Ruta más corta)
  • Algoritmos para hallar un árbol de expansión mínima en grafo no dirigido (Prim, Dijkstra, Kruskal)
  • Ramificación y poda (Backtracking)
  • Algoritmo de Ford Fulkerson para cálculo de flujo máximo
  • Bipartite matching (Solución mediante algoritmo de flujo máximo), aplicación a maximum vertex cover para grafos bipartitos
  • Teorema de flujo máximo-corte mínimo
  • Implementación mediante arreglos de queue, stack y algo similar a una deque :p.
  • Interval Tree
  • Binary Indexed Tree
  • Algoritmo Monotone Chain para hallar el Cerco Convexo(Convex Hull)
  • Estructura de datos para conjuntos disjuntos (Union-Find, Union by depth, Path compression, union by rank)
  • Exponenciación de matrices en tiempo logarítmico
  • Eliminación gaussiana
  • Criba de Erastostenes
  • Test de primalidad
  • Manipulación de bits (Bitwise)
  • Combinatoria : permutaciones con y sin repetición, combinaciones con y sin repitición
  • Ordenamiento : Bubblesort, Insertion sort, merge sort, quicksort
  • Búsqueda binaria
Cosas que creo que necesito aprender o practicar más ...

  • STL : list, multiset, bitset,
  • Algoritmo KMP para búsqueda de una cadena en un texto
  • Algoritmo Aho-Corasick para búsqueda en texto
  • Geometría Computacional (Sweep line, ...)
  • DFS, aplicación a punto de articulación en un grafo y componentes fuertemente conexas
  • Algoritmo de Dinic para cálculo de flujo máximo
  • Algoritmos para flujo máximo de costo mínimo
  • Teoría de Juegos (Nim, ...)
  • Estructura de datos para árboles binarios balanceados
  • Quadtrees
  • Corte Mínimo en una red de flujo
  • Algoritmo húngaro
  • Test de primalidad, algoritmos no deterministas
  • Algoritmo simplex
  • Algoritmo de Edmonds
  • Non-bipartite matching
  • Tries
  • Algoritmos alternos para bipartite matching
  • Transformada rápida de Fourier (Probar código en problemas)
  • Algoritmo de Karutsaba

Empezando...

Para empezar unos datos generales sobre quien soy y que podria ser mi motivacion para ir desarrollando este blog. Mi nombre es Mario Ynocente Castro (MarioYC), estudio Ingeniería de Sistemas en la Universidad Nacional de Ingeniería en Lima, Perú, actualmente tengo 19 años (recien cumpliditos :p).

A ver veamos que me llevo a empezar esto (tengo que tenerlo bien claro yo mismo), luego de un año en la Universidad (2008) di el examen para postular al grupo que se prepara para la ACM ICPC, en esos tiempos (ya sueño a viejo) conocia poco o nada de programación, y bueno empezaron las clases aprendimos algunas tecnicas de algoritmos como programacion voraz, programación dinámica, busqueda en grafos (bfs y dfs), ruta más corta en un grafo (algoritmos de dijkstra, Floyd - Warshall), le fui agarrando el gusto ya que necesita a mi parecer mucha imaginación, dedicación y una dosis de matemática :). Bueno luego de un tiempo empeze a participar en Topcoder, y ahi tuve mi primera vez (:0) en un concurso de programacion (especificamente de algoritmos), luego a fines de julio vino la Google Code Jam en la cual llegue a la Online Round 2 (no tan mal, no tan bien), luego en noviembre la regional de la ACM ICPC, donde forme parte del equipo "//Quitale el freopen!", junto con Roy David Palacios Rezza(roypalacios) y Ricardo Rafael Zarate Aima(rrza1), logrando el primer puesto de la Sede Peruana con 6 problemas resueltos y el noveno puesto a nivel de Sudamérica, quedandonos a un problema de lograr el pase a las finales mundiales en Suecia.

Bueno, este blog me servira de memoria de apoyo, y espero sirva de consulta a otras personas.