Problema: Dada una cadena $S$, $1 ≤ |S| ≤ 1000000$, y una operación $reemplaza(a, b)$ que reemplaza todas las ocurrencias del caracter $a$ por $b$ en $S$. Encontrar el mínimo número de aplicaciones de ella para que $S$ se convierta en un palíndromo.

Solución: A primera instancia parece un problema relativamente sencillo y conocido (la distancia de edición), sin embargo a pesar de que ese algoritmo nos da una solución, no es la óptima siempre puesto que no toma en cuenta la operación $reemplaza$ definida previamente. Para resolver este problema es necesario representarlo de una manera totalmente distinta: usando un grafo en el que cada caracter es un nodo y la aplicación de la operación $reemplaza$ entre ellos forma una arista.

Tomemos la cadena trestristestigres para desarrollar un ejemplo. Para resolverlo, debemos ver que cada letra del lado izquierdo se debe cambiar por una del lado derecho o viceversa para que se forme un palíndromo. Comenzaremos con la t más a la izquierda y la s más a la derecha, mira la tabla:

     _               _
     trestristestigres
    

     __             __
     trestristestigres
    

 ___           ___
     trestristestigres
    

 ____         ____
     trestristestigres
    

 _____       _____
     trestristestigres
    

 ______     ______
     trestristestigres
    

 _______   _______
     trestristestigres
    

 ________ ________
     trestristestigres
    

Debemos notar que a pesar de que en este caso una única componente incluye todos los nodos, podría suceder que no fuera así, y que los nodos estuvieran repartidos en distintas componentes.

Ahora, gracias a la ayuda del grafo podemos ver más sencillamente las transiciones que debemos hacer para convertir nuestra cadena en palíndromo, sin embargo también podemos observar que hay bucles inútiles, que si bien nos llevarían a una solución esta no sería la óptima. Usando $reemplaza(i, t)$, $reemplaza(e, r)$, $reemplaza(r, t)$, $reemplaza(g, s)$ y $reemplaza(s, t)$ la cadena original trestristestigres se convierte en ttttttttttttttttt que es un palíndromo. Tenemos que eliminar los bucles, haciendo uso de algún algoritmo (por ejemplo el de Kruskal) para convertir nuestro grafo en un árbol, por ejemplo este:

Complejidad: $O(N)$, $N$ es la longitud de la cadena $S$ (formar el grafo es $N/2$, buscar las componentes conexas es $N$).

Link del problema: 1010 - ACM contest and Blackout

Dificultad: Medio

Problema: El problema se resume a dar los dos árboles de expansión mínima o los árboles con el menor peso dada una entrada de N $ 3<= N <= 100 $ nodos (escuelas) y M aristas (conexiones).

Ejemplo: Para cada M línea sea darán 3 números Ai, Bi y Ci. Donde Ai y Bi serán las escuelas conectadas y Ci su precio para que estén conectadas.

4 5
4 1 4
4 2 7
1 3 1
1 2 5
3 2 6
Aquí el grafo original:

Las respuestas serían 10 y 11 ya que los arboles menos costosos se pueden formar así:



Ahora, ¿cómo conseguir esto?
Solución (algoritmo de Kruskal): 
Para los que no conozcan el algoritmo o no sepa como trabaja acá hay una buena explicación e incluso una implementación descargable muy entendible pues el mismo algoritmo usa la estructura de datos Union-Find.
Si bien obtener el MST (Minimum Spanning Tree) es fácil con Kruskal ¿como haríamos para asegurar el segundo árbol más barato? La idea básicamente es guardar las aristas con las que formamos nuestro primer MST y buscar formar árboles exceptuando cada una de las aristas una por una, es decir, quitamos una de las aristas y formamos un nuevo árbol, después la siguiente arista que guardamos y formamos otro árbol, siempre quedándonos con la MENOR.
Con una de las dificultades que me enfrenté es que al hacer kruskal omitiendo arista por arista no me aseguraba que se formara un árbol es ahí donde debemos comprobar que se forme un árbol efectivamente. ¿Cómo? en nuestro Union - Find podemos saberlo checando que solo haya una raíz, pues si solo hay una quiere decir que solo hay una componente conexa (que todos los nodos están conectados y forman el árbol).
Al hacer esto omitir arista por arista, checar que solo haya una componente conexa y quedarnos con la menor, nos dará el siguiente MST o árbol menos costoso.

En el siguiente fragmento de código lo que hago es conseguir omitiendo arista por arista tener el siguiente árbol de expansión mínima, checar que solo haya una componente conexa en el arreglo de padres y quedarme con la mínima:



Y bueno eso fue todo por esta ocasión, ya saben si gustan sugerir algún tema pueden hacerlo abiertamente y espero les haya gustado comenten si hay dudas y escriban. 
Adrián Fernández @ferprogramming

Dadas $N$, ($1 ≤ N ≤ 10000$) ubicaciones enteras $A_i$ ($0 ≤ A_i ≤ 10^9$) y un entero $K$ ($0 ≤ K ≤ 10^9$) para cada rana, determinar si la rana $A$ ubicada en la posición $i$ puede comunicarse con la rana $B$ en posición $j$. Las ranas en posicion $i$ y $j$ se pueden comunicar siempre que entre ellas la distancia sea  $ ≤ K$ o entre ellas existan otras ranas que cumplan con la anterior condición. Las ranas son muy amigas y entre ellas se pasan el mensaje.

Nos damos cuenta que cuando a una rana le llegue un mensaje esta se lo podría pasar a cualquiera otra que estuviera a menos de una distancia $K$ de su posición, por tanto partiendo de ese punto formaremos grupos de ranas que estarán comunicadas entre si, para lo cual usaremos union-find.

De entrada lo que debemos de hacer es ordenar las posiciones de cada rana, manteniendo el índice original en el cual estaban, posteriormente recorremos nuestro arreglo ya ordenado para unir a las ranas que se pueden comunicar.

Complejidad: $O(N log N)$ debido a la ordenación de las ubicaciones.

Para facilitarnos las cosas emplearemos un arreglo la clase pair, otro arreglo de enteros llamado roots (necesario para la estructura union-find y las funciones join y root habituales) y unas definiciones para darle un poco de claridad al código:

#define place second
#define distance first
typedef std::pair<int,int> frog;

for(int i = 1; i <= N; i++){
 roots[i] = i;
 scanf("%d", &frogs[i].distance);
 frogs[i].place = i;
}
std::sort(frogs+1, frogs+N+1);
for(int i = 1; i < N; i++){
 if(frogs[i + 1].distance - frogs[i].distance <= K){
  join(frogs[i + 1].place, frogs[i].place);
 }
}

Una vez terminada las uniones basta con leer las consultas y determinar si la rana $A$ se puede comunicar con la rana $B$:

root(a) == root(b) ? printf("Yes\n") : printf("No\n");