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.