Estructuras de Datos Piolas: LCA y Mo's Algorithm y PRACTICA

[marianocr...@gmail.com]

Ayer seguimos con la unidad de Estructuras de Datos Piolas

Al menos durante todo junio será los miércoles de 18:30 a 20 en el Laboratorio del DCC de FCEIA (Pellegrini 250).

Los temas que dimos fueron:

• LCA (Lowest Common Ancestor) en árboles. Como resolverlo con min range queries en O(1) (con un preprocesamiento en O(N logN)
• Mo's Algorithm, adjunto algún material para los que no pudieron venir:
  • Mo's algorithm explicado: https://cp-algorithms.com/data_structures/sqrt_decomposition.html#mos-algorithm
  • Mo's algorith en árboles (MUY AVANZADO): https://codeforces.com/blog/entry/43230 

La PRÁCTICA oficial del taller son los problemas que están en: https://vjudge.net/contest/562709 (password: "egipto2023" sin comillas)

Voy a agregar problemas todas las semanas a medida que demos temas.

La participación en dicha práctica puede ser tenida en cuenta en un futuro a la hora de dar prioridad a alumnos para apoyo económico para ICPC (por ejemplo pasajes al campamento de entrenamiento, etc).

Nos vemos el miércoles que viene!

Saludos

Mariano