MickyOr

Tecnica Small to Large

Nov 16th, 2020
118
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Creo que algunos llaman a la tecnica "Small to Large", es una clasica para union de conjuntos en O(N * logN)
  2.  
  3. Si queremos unir conjuntos y mantener informacion mas compleja que su tamaño o el maximo elemento (como en el problema), vemos que es parecido a union find pero solo eso no es suficiente para resolverlo.
  4.  
  5. Para eso haremos fuerza bruta inteligente. Si queremos unir un conjunto A con un conjunto B y sz[A] <= sz[B]
  6.  
  7. 1) Si ponemos los elementos de B en A -> O(N^2)
  8. 2) Si ponemos los elementos de A en B -> O(N * logN) :0
  9.  
  10. Siempre nos conviene añadir los elementos del conjunto pequeño al conjunto grande.
  11. La demostracion de esto es bien facil:
  12. - sz[A] <= sz[B]
  13. - Digamos C = A+B, entonces sz[C] >= 2*sz[A]
  14. - El tamaño del conjunto mas pequeño crece maximo logN veces
  15. - Revisar los elementos de A nos toma O(sz[A])
  16.  
  17. O(N * logN)! :D
RAW Paste Data