Charlas Certamen Nacional de OIA 2017

Guty · 22 Octubre, 2017 00:47

En este post iremos subiendo todo lo relacionado con las charlas que se dieron en el Certamen Nacional de OIA 2017.

BusquedaBinaria VentanasDeslizantes.pdf (1,8 MB)

Cómo resolver los problemas con vector y for

Juez Online (OIAJ)

Les recordamos la dirección al Juez Online de OIA. En el juez pueden realizar envíos de sus programas para que sean corregidos automáticamente.

http://juez.oia.unsam.edu.ar

Ahí hay varios problemas de práctica cargados en la categoría “Principiante”, para aquellos que comienzan a competir en los certámenes de programación. Recomendamos leer las “FAQ” antes de comenzar a utilizar el juez.

También hay problemas que fueron tomados en certámenes pasados en los que pueden realizar sus envíos.

Wiki de la Olimpíada

En la wiki se pueden encontrar explicaciones de distintos temas relacionados a los certámenes de programación. El link es:

http://wiki.oia.unsam.edu.ar/

Como todo, está en un proceso de continuo crecimiento y construcción. Así que es posible que los artículos de algunos temas todavía estén un tanto incompletos.

NicolasG · 19 Octubre, 2017 23:16

¿Donde se pueden ver los enunciados de este año?

Guty · 19 Octubre, 2017 23:52

Hola,

La idea es que los problemas del certamen estén subidos al juez en un futuro cercano. Cuando así sea, seguramente haremos un post en el foro avisando al respecto.

santo · 20 Octubre, 2017 11:48

¡¡Excelentes diapositivas!! Yo creo que esa “barrita indicadora” de la búsqueda binaria cambia vidas

Guty · 21 Octubre, 2017 16:34

santo · 21 Octubre, 2017 23:10

Como comentario menor sobre las diapositivas de Fenwick, en la diapo 53 se enuncian las propiedades que debe cumplir el operador \star para poderse utilizar con Fenwick. Falta mencionar una muy importante, pero que es tan común que solemos olvidarla, y es que el operador tiene que ser conmutativo: el orden de operaciones da lo mismo. Formalmente, a \star b = b \star a. Suma, máximo, mínimo, xor, producto (de números usuales), todas lo cumplen.

Si bien no es un caso común trabajar explícitamente en enunciados con operaciones no conmutativas (aunque podría ocurrir), operadores no conmutativos surgen muy naturalmente como parte de la solución de algunos problemas, y ahí Fenwick deja de funcionar, incluso ante updates monótonos y consultas de prefijos, ya que el update de fenwick aprovecha la conmutatividad.

Segment Tree en cambio funciona perfecto para estos casos, ya que tolera operador no conmutativo.

Ejemplos de problemas clásicos donde la resolución (pero no el enunciado) involucra muy naturalmente un operador no conmutativo:

Ninguno de los anteriores tiene updates monótonos con respecto al operador en cuestión (con mi versión de solución al menos :P), así que fenwick se rompe también por eso. Pero es posible armar versiones modificadas del problema, donde sí lo sean, y entonces se cumplirían todas las condiciones de la diapositiva 53, pero igual no se puede aplicar Fenwick porque el operador no conmuta y entonces no se puede hacer el update.