Problemas de la semana

UVA 315, Network : DFS, articulation points
UVA 796, Critical Links : DFS, bridge detection
UVA 10199, Tourist Guide : DFS, articulation points

Problemas de la semana

SRM 338 Div 1 Level 1 : Matemática
SRM 338 Div 1 Level 2 : Probabilidades, matemática (recurrencia)
SRM 339 Div 1 Level 1 : Simulación
SRM 339 Div 1 Level 2 : DP, probabilidades

UVA 11495, Bubbles and Buckets : Contar número de inversiones en O(nlgn)
UVA 11506, Angry Programmer : Min-cut

Stable marriage problem

Wikipedia
Computer Science Deparment at Princeton University
Live Arhive 3837
Live Archive 4463

Problemas de la semana

SRM 328 Div 1 Level 1: Matemática (Distancia de Manhattan) o Bfs o Simulación
SRM 328 Div 1 Level 2 : Greedy, Dfs
SRM 329 Div 1 Level 1 : Adhoc
SRM 329 Div 1 Level 3 : DP, probabilidades
SRM 330 Div 1 Level 1 : Simulación
SRM 331 Div 1 Level 1 : Bitwise
SRM 331 Div 1 Level 2 : Greedy
SRM 332 Div 1 Level 1 : Greedy
SRM 334 Div 1 Level 3 : Min cut
SRM 335 Div 1 Level 1 : Simulación, detectar overflow
SRM 335 Div 1 Level 3 : Precalcular, binary search
SRM 336 Div 1 Level 1 : Búsqueda
SRM 449 Div 1 Level 1 : Matemática (Área de un triángulo dados los vértices)

UVA 109, SCUD Busters : Geometría computacional, Convex Hull, punto en un polígono, área de un polígono
UVA 143, Orchard Trees : Geometría computacional, punto en un triángulo
UVA 634, Polygon : Geometría computacional, punto dentro de un polígono
UVA 10078, The Art Gallery : Gift-Wrapping, test para polígono convexo
UVA 10088, Trees on My Island : Geometría computacional, área de un polígono, teorema de Pick, mcd
UVA 10432, Polygon Inside A Circle : Área de polígono regular
UVA 11626, Convex Hull : Geometría computacional, Convex Hull
UVA 11646, Athetics Track : Matemática (Geometría, Trigonometría)
UVA 11648, Divide The Land : Matemática (Área del trapecio, ecuación cuadrática)

TJU 1011, Area : Geometría computacional, área de un polígono, teorema de Pick, mcd
TJU 1509, Taxi Cab Scheme : Bipartite matching, teorema de Dilworth
TJU 3122, Perfect Election : Precalcular, lógica proposicional
TJU 3124, Build Your Home : Geometría computacional, área de un polígono
TJU 3128, Internet Service Provides : Matemátices, maximizar función cuadrática

Live Archive 3837, The Stable Marriage Problem : Stable Marriage
Live Archive 4458, Compact Triangulation : DP (Triangularización óptima), Área de un triángulo
Live Archive 4462, Trip Verification : BFS
Live Archive 4463, Mentoring Assignment : Stable Marriage
Live Archive 4464, May the Right-Force be with you : BFS

Geometría Computacional

Geometry Algorithm Archive

Convex Hull

Si bien es cierto para resolver el problema del Convex Hull (Cerco convexo) de un conjunto de puntos en el plano me he acostumbrado a usar el algoritmo Convex Hull Monotone Chain el cual tiene complejidad O(nlgn) y cuyo código es bastante sencillo, pero nunca está demás aprender cosas nuevas.

Links:

Wikipedia
Ohio State University
Washington University in St. Louis
Convex Hull Algorithms Applet
Algorithmist
Fudan University
Optimal Output-Sensitive Convex Hull Algorithms in Two and Three Dimensions

Google Code Jam 2009 - Round 1

Bueno participé en la Ronda 1 A pero no clasifique, aprendí que la GCJ apenas tienes un algoritmo que puede resolver el small tienes que aprovecharlo.

No pude participar en la Ronda 1 B debido a que en esos momentos me encontrada dando el examen de la Olimpiada Nacional de Matemática Universitaria.

En la Ronda 1 C afortunadamente logre clasificarme para la Ronda 2, a pesar de que cometí un error tonto en la large de la A y envié otro output para la large de la C.

Sobre los problemas de esta ronda:

All Your Base : Greedy
Center of Mass : Matemática, minimizar una función cuadrática
Bribe the Prisoners : DP

Problemas de la semana

SRM 321 Div 1 Level 1 : Matemática simple, manejar casos
SRM 322 Div 1 Level 1 : Ordenamiento, greedy
SRM 325 Div 1 Level 1 : DP
SRM 326 Div 1 Level 1 : Matemática simple, parseo de cadenas

Problemas de la semana

SRM 316 Div 1 Level 1 : Greedy
SRM 317 Div 1 Level 1 : Recursión
SRM 319 Div 1 Level 1 : Simulación
SRM 447 Div 1 Level 1 : Simulación
SRM 447 Div 1 Level 2 : Minimum vertex cover, bipartite matching, max-flow

Google Code Jam 2009 - Qualification Round

Ya salieron los resultados de la Qualification Round, afortunadamente estuvieron bien mis outputs para los tres Large y terminé ubicado en el puesto 78, bastante bien en comparación con el año pasado, ahora a practicar para la ronda 1.

Sobre como resolvi los problemas:

Alien Language : Adhoc
Watersheds : Union-Find
Welcome to Code Jam : DP

Google Code Jam 2009 - Qualification Round

Hoy empezó la Google Code Jam 2009 con la Qualification Round, logré resolver para los tres problemas sus respectivos Small Input y envie mi output para los Large Input, esto me ubicó en el puesto 89, mañana se verá si me mantengo o si caigo en el ranking :p.

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

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

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.