Solucionario OBI San Agustin 17-10-19

Ubiquitous Religions - UVA 10583
Nos dicen que hay n personas y nos dan informacion del tipo "la persona A es de la misma religion que la persona B",
debemos calcular la maxima cantidad de religiones que hay entre las n personas.
El problema equivale a contar la cantidad de conjuntos donde, si A y B tienen la misma religion, pertenecen al mismo conjunto.
- CODIGO: https://ideone.com/dXgE3I

===========================

Balanced Rating Changes - CodeForces 1237A
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.
La solucion mas comun es la siguiente:
Observacion: la cantidad de numeros impares siempre sera par (no es dificil de demostrar, podria solo haber un numero impar?)

Ahora veamos que pasa con los numeros al dividirlos entre 2
Si a[i] es par   -> b[i] = a[i]/2
Si a[i] es impar -> b[i] = (a[i]+1)/2 o b[i]=(a[i]-1)/2

Sabemos que sumaTotal(a) = 0 y debemos hacer que sumaTotal(b) = 0
Veamos, sumaTotal(b) = ( sumaTotal(a) + (+1's y -1's de impares) ) / 2
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:
sumaTotal(b) = ( sumaTotal(a) + (+1 -1 +1 -1 ... +1 -1) ) / 2, que obviamente es igual a 0
- CODIGO: https://ideone.com/jXKSgs

===========================

Friends - UVA 10608
Muy parecido al primer problema.
En este caso la informacion es del tipo "la persona A y B estan en el mismo grupo de amigos".
Debemos encontrar el grupo de amigos con mas personas, debemos modificar el union-find clasico.
El elemento representativo del conjunto nos puede brindar mas informacion ademas de "yo soy el elemento representativo del conjunto :v".
Haremos que guarde la cantidad de elementos que pertenecen al conjunto de la siguiente manera:
int P[30000]; // padre
int SZ[30000]; // tamaño del conjunto

int findParent(v) {...}
void _union(int a, int b)
{
	a = findParent(a);
	b = findParent(b);
	if (a == b) return; // si a y b ya estan en el mismo conjunto, no hacemos nada
	P[a] = b; // hacemos que b sea el representante del nuevo conjunto grande
	SZ[b] += SZ[a]; // Al tamaño del antiguo conjunto de b, le añadimos los elementos del antiguo conjunto de a
}

Luego solo debemos buscar el maximo valor en SZ.
- CODIGO: https://ideone.com/nwEm8p

===========================

Chocolates - Codeforces 1139B
Hay dos condiciones de las que si o si se debe cumplir alguna para CADA posicion i del arreglo:
- x[j] = 0 para 1 <= j < i
- x[j] < x[i] para 1 <= j < i
Esto nos obliga a tener que comprar 0 chocolates por algunas tiendas, y luego comprar chocolates de forma estrictamente creciente.
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?
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.
Elegimos ese valor y vamos modificando los de la derecha haciendo cumplir las condiciones.
Ej:
Disponible = {1 2 1 3 6}
Comprados  = {0 0 1 3 6}

Disponible = {10 3 11 9 7}
Comprados  = { 2 3  5 6 7}

Disponible = {3 3 3 3 3 3 3}
Comprados  = {0 0 0 0 1 2 3}

Ahora solo debemos simular el proceso.
- CODIGO: https://ideone.com/JzCAyo

===========================

Ancient Berland Roads - CodeChef ABROADS
Me haria muy feliz si alguien logra resolverlo hasta la siguiente clase, asi que solo les dare pistas :)
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?
Hint 2: Y si solo hubieran queries del tipo D k? Seria mas facil se se construyeran caminos en vez de destruirse?