MickyOr

Solucionario OBI San Agustin 17-10-19

Oct 23rd, 2019
69
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. Ubiquitous Religions - UVA 10583
  2. Nos dicen que hay n personas y nos dan informacion del tipo "la persona A es de la misma religion que la persona B",
  3. debemos calcular la maxima cantidad de religiones que hay entre las n personas.
  4. El problema equivale a contar la cantidad de conjuntos donde, si A y B tienen la misma religion, pertenecen al mismo conjunto.
  5. - CODIGO: https://ideone.com/dXgE3I
  6.  
  7. ===========================
  8.  
  9. Balanced Rating Changes - CodeForces 1237A
  10. Hay muchas formas de resolver el problema ya que es simular el proceso de alguna forma que la suma de cambios de rating siga siendo 0.
  11. La solucion mas comun es la siguiente:
  12. Observacion: la cantidad de numeros impares siempre sera par (no es dificil de demostrar, podria solo haber un numero impar?)
  13.  
  14. Ahora veamos que pasa con los numeros al dividirlos entre 2
  15. Si a[i] es par -> b[i] = a[i]/2
  16. Si a[i] es impar -> b[i] = (a[i]+1)/2 o b[i]=(a[i]-1)/2
  17.  
  18. Sabemos que sumaTotal(a) = 0 y debemos hacer que sumaTotal(b) = 0
  19. Veamos, sumaTotal(b) = ( sumaTotal(a) + (+1's y -1's de impares) ) / 2
  20. Debemos hacer que la suma de los +1's y -1's de los impares sea 0, ya que hay una cantidad par de numeros impares, podemos intercalar +1's y -1's y obtendremos:
  21. sumaTotal(b) = ( sumaTotal(a) + (+1 -1 +1 -1 ... +1 -1) ) / 2, que obviamente es igual a 0
  22. - CODIGO: https://ideone.com/jXKSgs
  23.  
  24. ===========================
  25.  
  26. Friends - UVA 10608
  27. Muy parecido al primer problema.
  28. En este caso la informacion es del tipo "la persona A y B estan en el mismo grupo de amigos".
  29. Debemos encontrar el grupo de amigos con mas personas, debemos modificar el union-find clasico.
  30. El elemento representativo del conjunto nos puede brindar mas informacion ademas de "yo soy el elemento representativo del conjunto :v".
  31. Haremos que guarde la cantidad de elementos que pertenecen al conjunto de la siguiente manera:
  32. int P[30000]; // padre
  33. int SZ[30000]; // tamaño del conjunto
  34.  
  35. int findParent(v) {...}
  36. void _union(int a, int b)
  37. {
  38. a = findParent(a);
  39. b = findParent(b);
  40. if (a == b) return; // si a y b ya estan en el mismo conjunto, no hacemos nada
  41. P[a] = b; // hacemos que b sea el representante del nuevo conjunto grande
  42. SZ[b] += SZ[a]; // Al tamaño del antiguo conjunto de b, le añadimos los elementos del antiguo conjunto de a
  43. }
  44.  
  45. Luego solo debemos buscar el maximo valor en SZ.
  46. - CODIGO: https://ideone.com/nwEm8p
  47.  
  48. ===========================
  49.  
  50. Chocolates - Codeforces 1139B
  51. Hay dos condiciones de las que si o si se debe cumplir alguna para CADA posicion i del arreglo:
  52. - x[j] = 0 para 1 <= j < i
  53. - x[j] < x[i] para 1 <= j < i
  54. Esto nos obliga a tener que comprar 0 chocolates por algunas tiendas, y luego comprar chocolates de forma estrictamente creciente.
  55. Para que la cantidad de chocolates que compremos sea la mayor posible, decimos que el ultimo chocolate que compremos sea el mayor posible. Cual es este valor y por que el ultimo?
  56. Debe ser la tienda de mas a la derecha porque esa tienda "controla" los valores de todas las demas. Tomamos todos los chocolates que tenga disponible.
  57. Elegimos ese valor y vamos modificando los de la derecha haciendo cumplir las condiciones.
  58. Ej:
  59. Disponible = {1 2 1 3 6}
  60. Comprados = {0 0 1 3 6}
  61.  
  62. Disponible = {10 3 11 9 7}
  63. Comprados = { 2 3 5 6 7}
  64.  
  65. Disponible = {3 3 3 3 3 3 3}
  66. Comprados = {0 0 0 0 1 2 3}
  67.  
  68. Ahora solo debemos simular el proceso.
  69. - CODIGO: https://ideone.com/JzCAyo
  70.  
  71. ===========================
  72.  
  73. Ancient Berland Roads - CodeChef ABROADS
  74. Me haria muy feliz si alguien logra resolverlo hasta la siguiente clase, asi que solo les dare pistas :)
  75. Hint 1: Como resolverian el problema si solo hubieran queries del tipo P A x? Seria util un set o alguna estructura de datos extra?
  76. Hint 2: Y si solo hubieran queries del tipo D k? Seria mas facil se se construyeran caminos en vez de destruirse?
RAW Paste Data