En el problema:
http://juez.oia.unsam.edu.ar/#/task/red/statement
Basicamente tengo un problema de optimización ya que el tiempo se va al doble con la solución que envié.
Estuve viendo el tema de Union Find (en OIA Wiki) que es una etiqueta que propone el mencionado problema pero no termino entender que propone. Leí varias veces y pude comprender más o menos pero me pierdo en la parte del código, no se que realiza cada función y procedimiento.
Me gustaría que alguien me explicara el tema y asi poder programar una solucion óptima al problema. Muchas gracias.
1 me gusta
En general la estructura de Union-Find nos permite mantener una colección de conjuntos. Si tenemos n objetos, inicialmente arrancamos con n conjuntos todos de un elemento.
Las operaciones que realiza eficientemente es unir dos conjuntos y responder si dos elementos pertenecen actualmente al mismo conjunto. Para eso, la idea clave es mantener para cada conjunto un representante.
Quizá lo que no se entiende es a qué se le llama padre y por qué cada conjunto es un árbol
Te dejo un dibujito con el que creo que se va a entender. Originalmente hay 3 conjuntos \{2,3,6,8\}, \{1,4,7\} y \{5\}. Los representantes en este ejemplo serían, 2,4 y 5 respectivamente. Fijate que cada conjunto es un árbol.
Para ver si dos elementos pertenecen al mismo conjunto hay que subir en el árbol hasta encontrar el representante del conjunto al que pertenece cada elemento. Si queremos unir dos elementos la optimización que nos sugieren es cambiar el representante del conjunto más chico por el del conjunto más grande (donde el tamaño viene dado por la cantidad de elementos). Eso nos asegura que dado un elemento nunca tengamos que subir más de \mathcal{O}(\log n) veces para llegar a su representante. En el ejemplito quedaría así unir a los dos conjuntos más grandes.
Espero que ahora se entienda un poco mejor y que haya sido de ayuda.
3 Me gusta
¡Más claro imposible!
Muchas gracias
2 Me gusta
De nada, me alegro que haya sido de ayuda 
Aprovecho para mencionar que me parece muy bueno haber hecho algo similar a :
- Intentar primero el problema en el juez
- Ver las etiquetas del problema
- Ir a la wiki para ver el tema propuesto por la etiqueta.
- Preguntar en el foro en caso de haber alguna duda.
Si algo no está del todo claro siempre está bueno preguntar. En general va a haber alguien en el foro con buena predisposición que responda a la brevedad.
3 Me gusta