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