El 10 de noviembre se realizo el Regional ACM ICPC – South America 2012. Fueron 10 problemitas. Compitiendo contra paises como Argentina, Bolivia, Chile, Uruguay.
Aun no se publica los resultados oficiales en http://icpc.baylor.edu/public/worldMap/1482 pero tenemos un excel con los resultados de los otros paises 🙂 http://coj.uci.cu/downloads/files/Latam2012-Ranks.xlsx
Felicitaciones a los equipos que pasaran al ACM World Final en Saint petersburg «Buen Kilo de Pan Flauta» Argentina UBA ( nicoelrulo , Fixman , Pablo Blanc) resolvieron 8 problemitas (3 en la ultima hora) y a mi team «Los Desempleados FIIS» Perú – UNI ( MarioYc , hamlet_fiis , Predimonio ) con 7 problemitas. Por wildcard tambien pasaria el equipo Bahia (UNS) de Argentina. Al menos estos son los equipos clasificados hasta el momento.
Estuvieron xeveres los problemas. pueden practicar en el UVA los problemas son del 12524 – 12533
Adjunto mis soluciones. https://www.dropbox.com/sh/zn5xjzexyzz4it4/czBzgW5dFE
Arranging Heaps Dp +Dualidad Linea Punto Medio Dificil Boxes and Stones Dp Dificil Cellphone Typing Trie Facil Different Digits AdHoc Muy facil Environment Protection Integracion Simpson Medio-Facil Fix the Pond Componentes conexas – Union Find Facil Game of Tiles Bipartite Matching Medio Dificil Hours and Minutes AdHoc Muy facil Interval Product Segment Trees o BIT Muy facil Joining Couples LCA Medio
Analisis
Arranging Heaps Este problema es facilmente formulado como una dinamica en O(n*n*k) esta complejidad nos daria TLE. El problemita sale con esta observacion. Vamos a representar la recta (Xi*m+Yi) como un punto (Xi,Yi).
el teorema dice al construir el lower hull de esos puntos.
Se demuestra que el minimo de (Xi*m+Yi) se encuentra en las imagenes de los puntos que se encuentran en el lower hull.
Del dibujo el menor valor estara en alguna de las imagenes de (x1,y1), (x3,y3),(x8,y8),(x11,y11), (x13,y13)
Para no evaluar todo podemos encontrar el minimo con un ternary search sobre el valor de las imagenes de los puntos en el lower hull.
Otra recomendacion es como construyes el lowerhull los xi debes añadirlo en orden decreciente o creciente.
Sabiendo esto nos enfocamos al problema. sea w[i] peso. x[i] posicion . W[i] acumulado de w. G[i] acumulado de w*x . dp(pos,k)= encontrar un j>=pos tal minimices SUM[i=pos,j]( W[i]*(x[j]-x[i]) )+ dp(j+1,k-1)
= SUM[i=pos,j](w[i]*x[j]-w[i]*x[i] ) +dp(j+1,k-1) utilizamos los acumulados para reducir las sumatorias
= x[j]*(W[j]-W[pos-1]) -(G[j]-G[pos-1])+dp(j+1,k-1)
= (-x[j]*W[pos-1]) + X[j]*W[j]- G[j]+dp(j+1,k-1) +G[pos-1]
dado un pos y k necesito tener todos los puntos de todos los j>=pos. (por eso haremos un dp iterativo) . G[pos-1] es cte.
El punto seria (-X[j] , X[j]*W[j]- G[j]+dp(j+1,k-1)) y la pendiente seria W[pos-1].
Boxes and Stones Si solo hay una bolita en la caja B-1.
Entonces carol siempre podra eliminarlo y ganara
Si hay 2 bolas en la caja B-1. Paul escogera 1 bola.
carol eliminara la otra y movera el otro a la caja B. Carol perdera si hay al menos 2 bolas en la caja B-1
Si hay solamente 16 bolas en la caja B-4. Paul escogera 8 bolas.
Carol la eliminara y moveran 8 a la caja B-3. luego 4 caja B-2 . 2 caja B-1 del analisis anterior si hay al menos 2 en la caja B-1 Carol perdera.
Es como ver cada caja con un peso distinto. caja B-i tiene un peso de 1/(2^i)
Carol ganara si y solo si se cumple esto.
(xn+(xn-1+(xn-2+(…)/2)/2)/2)/2 ==0
division entera. facilmente se puede resolver con un DP O(n^3). precalculado.
Construimos el Trie de todas las palabras. para el caso de ejemplo. 4 hello hell heaven goodbye.
Al construir el trie almacenaremos tambien por cada nodo la cantidad de veces que han sido visitados. Esto es la cantidad de palabras que tienen el mismo prefijo.
La observacion va si recorremos con un dfs y no vemos un cambio entre 2 nodos consecutivos (cant visitados). Entonces no es necesario pulsar la tecla puesto que para ir al siguiente nodo. solo se hara de una unica manera. En otro caso si sera necesario teclear.
Different Digits Precalculamos el acumulado de los numeros que tengan digitos diferentes (fuerza bruta). contestamos en O(1) cout<<F[b]-F[a-1]<<endl;
Environment Protection Dado las funciones p(x) y q(x) donde para cada xi se cumple que p(xi)>q(xi). Debemos trazar una linea horizontal de tal forma que el area que comprende p(x) , la recta y q(x) sea exactamente A. Ver el dibujo del statement.
p(x) y q(x) son dificilmente integrables. Asi que utilizaremos otro metodo de aproximacion a la integral, debido a la cantidad de iteraciones que debemos hacer para tener un error menor a 10^-5 usaremos la regla de Simpson. http://es.wikipedia.org/wiki/Regla_de_Simpson
La recta horizontal la podemos fijarlo con un binary search ya que si la recta esta mas abajo nos asegurara un area mayor o igual.
Fix the Pond como necesitamos visitar todos los nodos, para ir de una componente conexa a otra debemos
rotar las barreras. La respuesta es cantidad de componentes conexas-1. (cuidado con hacer dfs para saber cuantas componentes hay, puede dar RTE por volcar la pila. Usar BFS o Union ,Find)
Coloreamos como un tablero de ajedrez. Notese que hay obstaculos. Habran diferentes componentes conexas y el jugador 1 es libre en escoger el que quiera. El jugador 2 ganara si y solo si en todas las componentes se trata de un perfect matching esto es la cantidad de 1s= cantidad de 2s = bipartite matching (hopcroft_karp).
esto es porque para cada 1 tendra un par que puede elegir siempre. por lo que siempre terminara jugando el jugador 2.
Hours and Minutes Con fuerza bruta precalculamos todos los angulos formados fijando la hora y minuto. el angulo de la hora sera 30*h. y del minuto 30*m+ 6*(h/12). Contestamos en O(1) si ese angulo ha sido visitado.
Interval Product Tenemos 2 operaciones. Actualizar un elemento y Contestar si XI x XI+1 x … x XJ-1 x XJ
es positivo , negativo o cero.
Para evitar el overflow , y porque solo nos piden el signo. si Xi>0 es lo mismo que Xi=1 . y Si Xi<0 es lo mismo que un Xi=-1
es un segment trees simple tree[node]=tree[v1]*tree[v2]. v1 hijo izquierdo , v2 hijo derecho
Joining Couples
Para darnos cuenta de las propiedades del grafo construyamos un caso mas completo.
Cada nodo tiene exactamente un hijo. pero puede tener mas de un padre. Cosa contraria en un arbol. Ademas como la cantidad de nodos = cantidad aristas. Esto siempre te asegurara exactamente un ciclo por cada componente. Para trabajar como un arbol procedemos a invertir la direccion de cada arista. y vamos a considerar A todo el ciclo como si fuera un solo nodo. y que este sea a su vez el nodo raiz.
Primero debemos encontrar el ciclo esto se da al añadir una arista el FIND(v1)==FIND(v2) si vamos a añadir una arista a dos 2 nodos que estan en la misma componente entonces se formara un ciclo.
Luego dado cualquier nodo de un ciclo. si recorremos sus padres entonces podremos. recorrer todo el ciclo. Esto para etiquetarlos con un valor (1,2,3,4,5,6) y saber el tamaño de este ciclo.
Dada un query (C,D) el LCA es (E) si este nodo no esta en el nivel 0 (o sea no es nodo raiz , por lo tanto no pertenece al ciclo ) la respuesta seria nivel(C)+nivel(D)-2*nivel(LCA(C,E))
En el caso del query (A,B) el LCA estaria en la raiz. estaria compuesta por (X,Y). la respuesta seria nivel(A)+ nivel(B)+distancia(X,Y). la menor distancia entre X,Y es el min( abs(etiqueta(X)-etiqueta(Y)) , tamciclo- abs(etiqueta(X)-etiqueta(Y)) ) . Nota etiqueta(X)=2 , etiqueta(Y)=4 tamciclo=6 en el dibujo 🙂
Good luck and have fun! Nos vemos en Saint Petersburg , Saludos hamlet_fiis
Algorithms for Chocos 
Snoopy
12 diciembre, 2012 at 11:18
El problema H, se podía resolver comprobando la divisibilidad por 6 (n % 6 == 0 ).
afruizc
22 junio, 2013 at 11:01
Un saludo.
En el problema E, en el ciclo que se usa para calcular la integral de todos los intervalos que van desde [a, a+EPS], porque la condición de terminación se necesita a+EPS < W + 1e-9. Yo entiendo que sin esto no funciona, pero realmente no entiendo porque. Además, haciendo varias pruebas, me he dado cuenta que con la condición puesta así a+EPS-1e-4 < W también da AC.
Me podrías por favor explicar el porqué de esto.
Muchas Gracoas
hamletov
25 junio, 2013 at 4:49
Lo que se desea hacer es calcular la integral para intervalo desde [0,W]
para ello dividimos en (10^4)*(W) partes de (10^-4) ,EPS cada uno.
el criterio de finalizacion se da cuando a+EPS<W + 1e-9 el cual es lo mismo a+eps=W es decir que se haya llegado al final
lo hago por que la comparacion de numeros reales no es exacta.
Otra forma seria hacer esto
for(int i=0;i<10000*w;i++,ini+=dif)
sum+=(f(ini,me)+4*f(ini+dif/2,me)+f(ini+dif,me) )/6.0;
Reemplazar en el codigo adjunto 🙂
Saludos,
Germán
6 agosto, 2013 at 22:37
Disculpa, pero no logro entender como defines la estructura para el trie.
Yo particularmente creé las clases Nodo y Trie definiendo una estructura recursiva, y logré resolver el problema. Pero mi código es más largo y más sencillo de introducir errores al codificar.
Por lo que entiendo tu propiedad trie sería una matriz de adyacencia, pero no logro comprender las demás estructuras ni cómo es que cargas los datos.
Te agradezco si puedes darme una pequeña explicación.
Saludos
hamletov
7 agosto, 2013 at 7:59
Hola, en un intento de explicar Aho Corasick a la gente de mi Universidad prepare estas diapos donde esta explicado como implemento el Trie.
https://www.dropbox.com/s/77cdkj6545c4lrc/aho%20corasick.ppt