El 14 de noviembre se realizo el Regional ACM ICPC – South America 2016
Los resultados fueron publicados en https://icpc.baylor.edu/regionals/finder/southamerica-south-2016/standings
Felicitaciones a los equipos de la region que pasaron al World Final 🙂
[UBA/ARG] PUMMAS – 9 problemas
[PUCP/PERU] O(1) O(n) O(u(n)) – 8 problemas
[FAMAF/ARG] Gracias Demetrio – 8 problemas
Hay problemas muy bonitos, aun no lo suben en el UVA , pero pueden enviar aqui.
https://www.urionlinejudge.com.br/judge/en/problems/all?page=54 (problems 2345-2354)
Los datos de entrada y salidas oficiales, se encuentran en este link http://maratona.ime.usp.br/resultados16/
Adjunto las soluciones: soluciones
Trivial, Dado 4 numeros (A<=B<=C<=D) te piden formar 2 grupos tal que la diferencia en la suma de cada grupo sea minima. Esto se obtiene con los grupos [A,D] y [B,C]
Back to the Future (Greedy, estructura de datos)
Consideremos que el grafo de la entrada sea la respuesta.
Paso 1: Si algun nodo tiene grado menor a A, entonces este debe ser eliminado. (puesto que no hay manera de que su grado aumente)
Paso 2: En caso de que no haya nodos de grado menor a A, busquemos el nodo con mayor grado si este es mayor a B entonces debe eliminarlo del grafo (Luego de esto repetir el paso 1).
Para resolver el problema eficientemente en O(MlogM) hacemos uso del STL (SET).
set<int>adj[100001]; — adj[i] me envia los nodos a los cuales esta conectado i. para eliminar en el enlace con el nodo j. Hacemos adj[i].erase(j); Para obtener el mayor y menor grado de todos los nodos mantenemos los tamaños en otro set
set<pair<int,int> >size;// first value= grado, second value= nodo al cual pertenece el grado dado.
Counting Self-Rotating Subsets
El set puntos que sea Self-Rotating debe ser un poligono regular. El unico poligono regular con coordenadas enteras es el cuadrado.
Por lo tanto debemos considerar solo los angulos de rotacion (90 y 180). Ademas podemos observar que los cuadrados pueden ser vistos como dos diagonales, de aqui solo consideraremos el angulo de rotacion de 180.
Para resolver el problema, tomaremos para cada par de puntos el mid-point como centro de rotacion, lo demás se puede calcular con combinatorias.
Dating On-Line (Greedy)
Te piden hallar el area total de un diagram radial, teniendo un conjunto de puntos S[i] de tamaño n.
El area total es igual a la suma de varios triangulos, 1/2*Si*S(i+1)* sin(pi*(n-2)/n). Debemos maximizar el area mediante una permutacion de S.
Para maximizar el producto nos conviene que el mayor numero se multiplique por el 2do mayor para que tenga un mayor aporte. Por lo tanto generaremos la siguiente permutacion. sea n=10 P9,P7,P5,P3,P1,P2,P4,P6,P8,P10 , donde Pi es el i-esimo elemento mas grande de S.
E (NOT FOUND)
Trivial, simular los movimientos del robot y contar cuantas veces ha pasado por la posicion S.
Game of Matchings (KMP) Analisis forifchen
Es suficiente hacer dos observaciones:
-Observación 1: Dos palabras mapean si las diferencias de una posición y la anterior aparición del caracter en dicha posición son iguales (o cero si es la primera aparición):
abbab -> 0 0 1 3 2
zxxzx -> 0 0 1 3 2
Denominémosla versión D, es decir, dos palabras mapean si sus versiones D coinciden.
-Observación 2: Una palabra mapea una subcadena de otra si la subcadena de la version D es equivalente a la palabra en version D. Donde la equivalencia del match se define como la equivalencia de cada elemento de la versión D, y esta se define con dos casos: si los elementos son iguales o si uno es 0 y el otro es mayor que la longitud del prefijo de la palabra hasta el elemento.
Por ejemplo:
abbababa -> 0 0 1 3 2 2 2 2
abcb -> 0 0 0 2
En versión D:
la subcadena 0 1 3 2 no es equivalente a la palabra 0 0 0 2, debido a que los elementos segundos son diferentes (1 != 0) y 1 no es mayor que la longitud del prefijo hasta el 1,es decir el prefijo [0] cuya longitud es 1. Notar que los elementos terceros si eran equivalentes puesto que uno es 0 y el otro es mayor que la longitud del prefijo hasta el 3, es decir el prefijo [0 1] cuya longitud es 2.
De modo que la solución es un KMP en las versiones D usando como matching la equivalencia definida por la segunda observación.
Hotel Rewards (Greedy)
Vamos a maximizar el total de costo ahorrado por el canje de free night en el hotel.
El algoritmo es muy corto y facil de entender 🙂
multiset<int>S;
for(int i=0;i<n;i++){
S.insert(P[i]);
int tam=(i+1)/(k+1); //cantidad de free-night en total para el dia (i+1)
while(S.size()>tam){
S.erase(S.begin());
}
}
Observaciones:
Entre el dia [1-K] no se puede obtener ningun free-night
Entre el dia [K+1-2K+1] solo se puede obtener un free-night este debe ser el maximo.
Entre el dia [2K+2-3K+2] se pueden obtener 2 free-night, ambos pueden pertenecer de ese intervalo o considerando uno del intervalo anterior si es que posee un costo mayor.
Internet Trouble (DP – Divide and Conquer Optimization)
Dado N ciudades debemos colocar K estaciones de internet(localizados en las ciudades) de tal manera de que minimicemos el costo de acceso a internet entre todas las ciudades. El costo de acceso a internet de la ciudad i es |i-j|, donde j es una estacion de internet.
Obviemos las constantes B y C definidos en el problema.
Podemos definir la relacion de recurrencia de la siguiente manera
DP(N,K) = min ( DP(i,K-1) + G( i,N) ). donde 0<=i<N
DP(N,K) , minimo costo habiendo colocado una estacion en N y quedandome K estaciones por poner. G(i,j) , costo de total de las ciudades entre <i,j> tal que hay 1 estacion en i y una estacion en j. (Esto se puede procesar en O(1) Podemos observar que la complejidad de este algoritmo de programacion dinamica es O(N^3) el cual no entra en tiempo. Por este motivo aplicaremos la siguiente optimizacion (Divide and conquer optimization) para resolverlo en O(N^2*log(N))
Leer: http://codeforces.com/blog/entry/8219 en donde se explica como se utiliza esta optimizacion
Problema de ejemplo: http://codeforces.com/contest/321/problem/E
Editorial en donde se explica detalladamente ese problema y la estrategia: http://codeforces.com/blog/entry/8192
—–Nota: Lamentablemente en este problema el juez URI tiene un dataset con errores, (Probar con el dataset oficial).
Nuestro coach se encuentra en la sala 1(Contest room) y se movera constantemente mediante un tunel hacia otra sala. (Cada sala tiene solo un tunel que dirige hacia otra sala). Cada movimiento toma 1 segundo
Dado N salas nos piden calcular T (T>=2 && T<=N) tal que se minimice la probabilidad de que la ultima sala visitada sea la sala 1.
Observamos, de que si la ultima sala visitada es 1, entonces esta se genera a partir de un ciclo de tamaño T o divisor de este, ya que la sala inicial es el #1.
Para minimizar la cantidad de ciclos entonces T debe ser primo y este debe ser maximo.
Kill the Werewolf (Maxflow)
Asumamos que el i-esimo jugador es el hombre lobo, debemos determinar si es posible que pueda salvarse dada las restricciones. (Repetir para cada i [0-n-1] ).
Observacion 1: Si algun jugador tiene como una de sus elecciones votar por el hombre lobo, entonces ellos votaran para matarlo.
Observacion 2: Si el lobo recibe K votos, entonces para que se salve todas las personas deben recibir cuanto mucho K-1 votos o en el caso de que alguno corresponda a la posible eleccion del lobo (el cual vota al final) debera recibir cuanto mucho K-2 votos.
De ambas observaciones armaremos el grafo, si el flujo maximo es igual a la cantidad de elecciones de las personas que faltan por votar entonces el lobo se salvara.
good luck & have fun
hamlet_fiis
Algorithms for Chocos 
Kun
7 diciembre, 2016 at 1:32
Gracias Demetrio -> 8 problems