Solución a “Mapas de bits”

Concurso: Preselectivo para la IOI 2014, Etapa 1, Problemset 12
Autor: Jorge Alberto González Martínez
Fuente: Jorge Alberto González Martínez

En el problema se describen dos formas de representar un mapa de bits.

La forma bidimensional es simplemente utilizar una matriz para representar los bits.
La forma por descomposición consiste en agrupar los bits similares y solo escribir el valor de los bits similares. En caso de que no sean similares todos los bits en un mapa de bits dado, se procede a dividir en cuatro secciones, imprimir la letra D y procesar cada uno de los cuartos de la misma manera, tal como se lee en la descripción del problema.

La solución a este problema consistía en programar el método descrito. Este método inherentemente está basado en la técnica de divide y vencerás.

A continuación, un pseudo-código que muestra la forma de llevar a cabo la transformación de un mapa de bits bidimensional a la forma reducida:


ReduceMapa(mapaDeBits)
Si todos los elementos en mapaDeBits son iguales
    Imprime el valor y termina
Si no
    Imprime D
    ReduceMapa(mapaDeBits.superiorIzquierdo)
    ReduceMapa(mapaDeBits.superiorDerecho)
    ReduceMapa(mapaDeBits.inferiorIzquierdo)
    ReduceMapa(mapaDeBits.inferiorDerecho)

El método para hacer la transformación inversa es muy parecido, sólo que para imprimir la equivalencia hay que comenzar con un mapa de bits bidimensional que nos sirva de variable auxiliar para hacer la conversión. Esta variable auxiliar se puede declarar de manera global y, cuando el método recursivo termine, simplemente imprimir su contenido:


AmplificaMapa(mapaDeBits, sección)
Si mapaDeBits comienza con un valor
    Rellenar sección del mapa bidimensional con el valor
Si no
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.superiorDerecha)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorIzquierda)
    AmplificaMapa(mapaDeBits.removerPrimerElemento, sección.inferiorDerecha)

La primera vez que se llama a la función AmplificaMapa se debe entregar la representación de la forma por descomposición del mapa de bits en la variable mapaDeBits y la sección que se entrega inicialmente es todo el mapa de bits. Esto puede ser manejado por filas y columnas.

A continuación se muestra una implementación en C++ que resuelve el problema. Nótese cómo se maneja la sección sobre la que se está trabajando con cuatro variables: tl_row, tl_col, br_row, br_col. El nombre de las variables proviene de top-left row, top-left colum, bottom-right row y bottom-right colum respectivamente. Representan los índices (fila,columa) de las esquinas superior izquierda e inferior derecha.

Solución a “Chilly Rapero”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12
Autor: Ethan Jiménez Vargas

La clave para resolver este problema es interpretar las palabras como nodos y los cambios entre palabras como aristas, de manera que podamos verlo todo como un grafo no dirigido. Asignamos a cada palabra un nodo y creamos las aristas entre nodos verificando alguna de las condiciones que se proponen en el enunciado del problema: si una palabra A es un prefijo o sufijo de la palabra B o la palabra A difiere con la palabra B por un solo caracter, establecemos una arista entre los nodos A y B.

Crear las aristas entre los nodos tiene una complejidad de O(LN2) y la manera más simple de almacenar dichas aristas es mediante una matriz de adyacencia. Ya que tenemos el grafo planteado, buscaremos la manera más rápida de cambiar de palabra entre cualquier par de palabras, esto puede conseguirse usando el algoritmo de Floyd-Warshall con una complejidad de O(N3) que es suficiente para el problema.

Finalmente, para obtener la respuesta sumamos el mínimo número de cambios requeridos entre todos los pares de palabras consecutivas en el rap, este número de cambios fue obtenido mediante el algoritmo de Floyd-Warshall. El número total de cambios lo multiplicamos por 0.2 y será la respuesta para el problema.

Complejidad de la solución: O(LN2+N3)

Solución a “Metro”

Concurso: Preselectivo para la IOI 2013, Etapa 1, Examen 12
Autor: Alain Acevedo Mejía

El problema en cuestión se reduce a encontrar un árbol de expansión mínima. La solución es una aplicación directa de alguno de los algoritmos existentes para ello (bien implementada), por lo que hablaré brevemente sobre una de las posibilidades y daré referencias donde puedan encontrar información más detallada.

Para encontrar el costo mínimo de unir todas las estaciones debemos encontrar el árbol de expansión mínima de la gráfica en cuestión (es decir, una subgráfica conexa que una todos los vértices de la gráfica original y cuyo peso (la suma de los costos de todas sus aristas) sea el mínimo posible (siempre es un árbol)). Para ello una opción es usar el algoritmo de Kruskal: Ordenamos las aristas por su peso y vamos agregando cada arista de peso mínimo que no cree un ciclo en la gráfica. Hacemos esto hasta haber conectado todos los vértices de nuestra gráfica. Por la cantidad de aristas que tenemos requerimos ordenar eficientemente y verificar si las aristas forman un ciclo o no eficientemente en cada paso, de lo contrario el programa no correrá en tiempo.

Para verificar si se forma o no un ciclo agregando una determinada arista empleamos el algoritmo conocido como Union Find, que se explica ampliamente en las secciones 16.7, 16.8 y 16.9 del libro Problemas y Algoritmos de Luis E. Vargas Azcona. Es importante mencionar que para obtener los 100 puntos en el problema es necesario implementar las optimizaciones que se mencionan (y aunque no fuera así no está de más que las conozcan).

Además del libro de Luis E. Vargas, que recomiendo ampliamente, sugiero la página de Pier Guillen http://pier.guillen.com.mx/ , que en ->Algorithms ->10. Gráficas ->10.6 Árboles Mínimos Generadores desarrolla el tema en cuestión. Y claro, no está de más que consulten el tema en el libro Introduction to Algorithms de Thomas H. Cormen, que en la tercera edición trabaja el tema en el capítulo VI. Graph Algorithms ->23 Minimum Spanning Trees.

El siguiente código resuelve el problema: