Training Camp Argentina 2018

30 Julio-10 Agosto, 2018 • Universidad de Buenos Aires

Sponsors

Platinum
Image
Image
Image
Silver
Image

Clases Teóricas

Charla de introducción al training camp.

Clases iniciales:

  • E/S + Introdución, a cargo de Agustín Santiago Gutiérrez
  • Búsqueda binaria y ordenamiento, a cargo de Quimey Vivas
  • Programación dinámica , a cargo de Mariano Crosetti. Mariano dictará un subconjunto de los siguientes temas, a definir y acorde al tiempo disponible: ¿Qué es la DP? Top Down y Bottom Up. Reconstruyendo la solución. K - ésima reconstrucción. Reducir una dimensión de memoria. Agregando una flag. Recuperando un parámetro. Dinámica en rangos. Dinámica en de máscara de bits. Dinámica en prefijos de números. Dinámica en frentes.
  • Matemática, a cargo de Ariel Zylber.
  • Grafos, a cargo de Matías Hunicken. Representación de grafos, árboles, DFS/BFS, distancias mínimas (algoritmos de Dijkstra y Floyd), union-find, algoritmo de Kruskal.
  • Estructuras de datos para programación competitiva, a cargo de Quimey Vivas.
  • Algoritmos golosos, a cargo de Pablo Zimmermann. Introducción a los algoritmos golosos/voraces. Cómo pensarlos. Estrategia para usarlos en competencias. Teorema de la fruta golosa y del ordenamiento de a 2 (Taravilse, Álvarez). Falsos positivos: Los Greedy que no son Greedy. Ejemplos y anécdotas personales.
  • Strings, a cargo de Agustín Santiago Gutiérrez. Arreglo Z (ejemplo, buscar un string en otro). Bordes de una cadena (calculados a partir del arreglo Z, por ejemplo para encontrar sufijos o prefijos palindrómicos eficientemente). Hashing de Rabin-Karp y trucos asociados (o "cómo usar hashing para computar casi cualquier cosa de strings", como por ejemplo todos los anteriores + el resultado del algoritmo de Manacher + el suffix array de un string). Tries.

Clases avanzadas:

  • Geometría computacional, a cargo de Melanie Sclar. Elementos básicos: puntos, vectores y rectas. Operaciones importantes y representación. Técnicas de barrido ("sweep line"): Par de puntos más cercano, Intersección de segmentos, Cápsula convexa (Convex Hull). Área de polígono y teorema de Pick.
  • Dualidad punto línea y "convex hull trick", a cargo de Agustín Santiago Gutiérrez "Convex hull trick" es una técnica conocida para calcular eficientemente "El máximo de varias funciones lineales", sobre un cierto valor de x. La dualidad punto línea es una forma de transformar problemas con rectas en problemas con puntos, y viceversa. Además de aprender ambas, usaremos esta última técnica para entender de dónde viene el nombre medio misterioso de "convex hull trick".
  • Flujo máximo , a cargo de Ariel Zylber. En la charla se tratarán algunos de los siguientes temas: Algoritmo para flujo máximo / corte mínimo, con énfasis en cómo utilizarlo para modelar y resolver problemas de competencias. Matching máximo bipartito. Teoremas de Konig y Hall. Mínima partición/cubrimiento por caminos. Teorema de Dilworth. Flujo de costo mínimo.
  • Matemática: Combinatoria y probabilidad, a cargo de Pablo Zimmermann. Introducción a la combinatoria. Formas de calcular números combinatorios. Principio de inclusión - exclusión. Nociones básicas de probabilidad en competencias. Introducción a Teoría de Juegos. Posiciones perdedoras. Nim y Misere Nim. Teorema de Sprague-Grundy.
  • Estructuras de datos sobre árboles, a cargo de Matías Hunicken. Heavy light decomposition, dsu on tree, centroid decomposition, link-cut tree.
  • Suffix Automaton, a cargo de Nicolás Álvarez. Suffix automaton: si bien ambas cosas son importantes, la charla se enfoca más en "cómo utilizar la estructura para resolver los problemas", y no tanto en "por qué se construye así el autómata". El suffix automaton es una estructura más avanzada y complicada, continuación natural de las estructuras básicas explicadas en la charla básica de strings.

Oradores

Nicolás Álvarez

Licenciado en Ciencias de la Computación de la Universidad Nacional del Sur. Estudiante del Doctorado en Ciencias de la Computación de la Universidad Nacional del Sur. Finalista como participante (2009) y como coach (2010, 2013, 2015) de la ACM ICPC. Jefe de Trabajos Prácticos en la Universidad Nacional del Sur.

Mariano Crosetti

Estudiante de licenciatura en ciencias de la computación en la UNR. Finalista ICPC con su equipo Caloventor en Dos en 2015 (Marruecos) y 2016 (Tailandia). Pasante en Google Codejam (miembro del staff de la final Dublín 2017) y Google Chromecast (2018).

Agustín Santiago Gutiérrez

Licenciado en Ciencias de la Computación de la Universidad de Buenos Aires. Finalista y campeón latinoamericano en dos ocasiones como competidor (2009 y 2011) y finalista en seis ocasiones como entrenador (2010, 2013, 2014, 2015, 2016 y 2017) siendo campeón latinoamericano en 2015. Agustín se desempeña como Ayudante de Primera en la carrera de Ciencias de la Computación de la Universidad de Buenos Aires - FCEN. Participó en dos ocasiones de la International Olympiad in Informatics (IOI) obteniendo una Medalla de Plata en 2007. Jurado y entrenador de la Olimpíada Informática Argentina (OIA).

Matias Hunicken

Estudiante de Licenciatura en Ciencias de la Computación en la Universidad Nacional de Córdoba. Finalista de ICPC en dos ocasiones (2017 y 2018).

Melanie Sclar

Licenciada en Ciencias de la Computación de la Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires. Entre otros premios, podemos destacar la Medalla de Plata en la 21° Olimpíada Matemática del Cono Sur (Brasil, 2010); Medalla de Bronce en la 26° Olimpíada Iberoamericana de Matemática (Costa Rica, 2011); Campeona Nacional en la 27° Olimpíada Matemática Argentina (2011). Finalista en dos ocasiones (2014 y 2015) de la ACM ICPC y Campeona Latinoamericana en 2015. Melanie fue pasante de Facebook (USA) en dos oportunidades.

Quimey Vivas

Doctor en Matemáticas de Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires. Finalista de la ACM-ICPC Finalista como participante (2010) y como coach (2012). Ex Ingeniero de Facebook en Menlo Park, California (USA). Trabaja en Avature.

Pablo Zimmermann

Estudiante de Licenciatura en Ciencias de la Computación de la Facultad de Ciencias Exactas y Ingeniería y Agrimensura, Universidad Nacional de Rosario. Entre otros premios, podemos destacar la Medalla de Oro en la 8° Olimpíada Iberoamericana de Mayo, Medalla de Bronce y Mención de Honor respectivamente en la 47° y 48° Olimpíada Internacional de Matemática (Eslovenia, 2006 y Vietnam, 2007), Medalla de Oro en la 15° Olimpíada Matemática Rioplatense (Escobar, Argentina). Finalista en dos ocasiones (Marruecos, 2015 y Tailandia, 2016) de la ACM ICPC y Campeón Latinoamericano en 2016. Coach Finalista en el 2017 (EEUU). Pablo fue pasante de Google (USA).

Ariel Zylber

Estudiante de la Licenciatura en Ciencias Matemáticas y Licenciado en Ciencias de la Computación de la Facultad de Ciencias Exactas y Naturales, Universidad de Buenos Aires. Entre los numerosísimos premios que obtuvo, podemos nombrar la Medalla de Oro en la 52° Olimpíada Internacional de Matemática (Amsterdam 2011), dos veces medalla de Oro en la Olimpíada Iberoamericana de Matemática (2011 y 2012), Medalla de Oro en la Olimpíada Matemática del Cono Sur (2010), medalla de Bronce en la 22° Olimpíada Internacional de Informática (Waterloo 2010); entre muchos otros. Finalista en dos ocasiones (2014 y 2015) de la ACM ICPC y Campeón Latinoamericano en 2015. Ariel fue pasante de Facebook (USA).