| CURSO ON-LINE DE PREPARACIÓN |
| Sesión 1.3. Tipos de problemas |
| CURSO ON-LINE DE PREPARACIÓN |
| Sesión 1.3. Tipos de problemas |
Las etapas más importantes en la resolución de un problema de un concurso de programación son las de comprensión e identificación del problema al que se enfrenta el programador.
En efecto, si no conseguimos comprender el problema es muy difícil, por no decir imposible, que consigamos resolverlo adecuadamente. Esta primera etapa de comprensión es tan sumamente extensa que apenas cabe dar algunos consejos de, digamos, sentido común. De ello nos encargaremos inmediatamente a continuación.
Una vez comprendido el problema, qué tarea es la que se espera que realice nuestro programa exactamente, el siguiente paso es su identificación. Prácticamente todos los problemas de un contest de programación caen dentro de alguna de las grandes categorías de problemas que vamos a analizar aquí. Conviene desarrollar la habilidad de identificar estos problemas, pues con ello tendremos una parte muy importante de la solución en nuestras manos. En este paso es básico un proceso de abstracción de los datos fundamentales del enunciado para poder determinar la categoría en la que englobar nuestro problema.
Cuando el problema ha sido debidamente comprendido e identificado, el último paso será particularizar (o instanciar) el esquema algorítmico apropiado para ese tipo de problemas a nuestro caso concreto. Para ello elegiremos el lenguaje de programación y escribiremos el programa. Este no es necesariamente un paso trivial en todos los casos, de hecho surgirán aquí docenas de detalles que deberemos cuidar si no queremos que un pequeño despiste en la codificación eche por tierra nuestro impecable estudio previo, pero sí que será mucho más guiado en general y podremos realizarlo con muchas más garantías de éxito que si atacásemos desde cero el problema sin detenernos a pensar sobre su naturaleza.
Como mencionamos en la introducción, esta es la piedra angular de todo el proceso de resolución del problema. Son tantos y tan diferentes los errores que un programador novel (y a veces los no tan noveles) puede cometer en este momento, que apenas es posible dar unas guías generales sobre cuáles son las trampas para osos donde con mayor frecuencia se puede caer:
Muchos enunciados comienzan por prolijas explicaciones del background del problema, generalidades y otros discursos que ejercen un efecto hipnótico en el lector (a veces de forma deliberada) que con frecuencia hacen que nos pasen desapercibidos determinados datos que aparecen dispersos casi como por "azar" en medio de tales discursos. Estos datos muy a menudo son clave para determinar (o descartar) ciertas estructuras de datos o esquemas algorítmicos que podrían ser utilizados con provecho (o ruinosamente) en la resolución del problema.
Por ejemplo, el problema 147 del archivo de la UVA, cuando describe la entrada dice, casi que de pasada, que las cantidades no serán nunca mayores de $300.00 y que serán múltiplos de $0.05. Este detalle dicho en este punto, donde no se describe el problema en sí mismo sino la entrada, lejos de ser algo "anecdótico" es fundamental para la resolución del problema.
Si a veces cometemos el error de desatender datos relevantes del problema, otro error no menos importante que también cometemos con cierta frecuencia y que constituye el reverso del anterior es hacer justo lo contrario: añadir restricciones que en el enunciado del problema no existen. Este error a veces viene inducido por el propio enunciado que parece sugerir, aunque nunca de forma explícita, ciertas restricciones; o por los ejemplos de entradas/salidas que se muestran y que en muchas ocasiones (muchas veces de forma deliberada) omiten ciertos valores, dando así la apariencia engañosa de que no han de ser considerados.
Algunas categorías generales de este tipo de error podrían ser las siguientes:
Rangos de valores: Por ejemplo, en el enunciado se habla de que la entrada consta de una serie de números. Por el enunciado del problema, y por los ejemplos de entrada y salida, parece que esos números han de ser positivos y así lo tomamos, cuando en realidad en ningún sitio se afirma que lo sean. Otro ejemplo típico de este error es considerar que cuando se habla de una matriz de N x M no se consideran los casos en que N o M (o ambos) pudieran ser 1.
Resultados pedidos: Por ejemplo, el enunciado nos pide que digamos si un determinado valor es par o impar, dando así la impresión de que debemos calcular ese valor y después decir si es par o impar, cuando es posible que podamos decidir si es par o impar indirectamente y sin necesidad de calcularlo. A veces es mucho más fácil determinar una propiedad del resultado que el resultado propiamente dicho. De hecho, calcular el resultado podría llegar a ser computacionalmente ruinoso para los propósitos de un contest de estas características.
Una vez que nos hemos asegurado de que hemos comprendido perfectamente el problema, que sabemos con exactitud qué se nos pide, cuáles son los datos de entrada y las características de éstos y cuáles son los datos de salida que se esperan de nuestro programa, el siguiente paso es la identificación del problema. En realidad, en la práctica este paso se da de manera simultánea con el anterior, pues el programador experto suele ir pergeñando la solución en su mente al mismo tiempo que va comprendiendo el problema. En aras de la claridad de la exposición, en esta presentación lo describiremos como un paso posterior al de comprensión. Para ello vamos a establecer dos clasificaciones, una por tipo de problemas y otra por tipo de algoritmo que resuelve el problema.
Cuando hablamos de tipo de problema nos referimos básicamente a la forma que el problema tiene en cuanto al modo en que se plantea. Haremos en esta sección una breve clasificación de los tipos de problemas más comunes en cuanto a su enunciado.
Problemas de ajedrez. El ajedrez es un tema recurrente en el planteamiento de problemas algorítmicos. Los movimientos de las distintas piezas que componen el juego, sobre todo del caballo, han servido de inspiración para el planteamiento de muchos problemas matemáticos y algorítmicos. Los problemas de ajedrez pueden ser modelados en general como problemas de grafos. Las 8 x 8 = 64 casillas del tablero pueden visualizarse como un grafo de 64 vértices cuya adyacencia dependerá, en general, de la pieza que se esté considerando mover. Existen, no obstante, variaciones de estos problemas que se refieren a tableros de tamaño diferente al tradicional de 8 x 8.
Esta consideración general de asimilar problemas de ajedrez con grafos es al mismo tiempo una trampa que a veces se tiende a los concursantes, pues con frecuencia aparecen problemas cuyos enunciados son de tipo ajedrecístico pero sus resoluciones no pasan por planteamientos de tipo grafo.
Como ejemplo, puede consultarse este problema de movimientos del caballo.
Codificación/Decodificación. En esta categoría englobamos problemas que se plantean como procesos de codificación o decodificación de determinados datos. Típicamente, aunque no siempre, los datos en cuestión son caracteres, y estos problemas suelen plantearse como códigos de cifrado para comunicaciones.
Este problema es un ejemplo típico de esta categoría.
Para este tipo de problemas lo normal es que el algoritmo que lo resuelve no deba hacer uso de estructuras de datos mucho más complejas que un simple array unidimensional o bidimensional, y en algunos casos ni siquiera eso.
Conversión de caracteres. Son problemas parecidos a los anteriores, casi un caso particular, con la diferencia de que los datos de entrada son caracteres y la codificación se realiza también en forma de caracteres. Habitualmente, cada ejemplar de entrada suele tener un tamaño máximo lo suficientemente pequeño para que pueda alojarse y manejarse en un array de caracteres o un string como los que proporcionan las librerías estándar de Pascal o C++.
Este problema es un ejemplo típico de esta categoría.
Cálculos de combinaciones/permutaciones. Se trata de problemas que piden calcular el número de combinaciones que pueden realizarse entre los elementos de un determinado conjunto que puede darse de forma explícita o implícita. Para abordar con éxito este tipo de problemas conviene observar cuidadosamente las características del problema y de la solución requerida, y en particular cuestiones como el orden de los elementos (si es relevante o no, es decir, si se trata de combinaciones o permutaciones), la repetición o no de un mismo elemento en una de las soluciones, etcétera. En general, conviene tener claros los conceptos matemáticos de combinatoria, pues estas diferencias no siempre quedan claras a la vista de los ejemplos de entradas y salidas que proporciona el enunciado.
Este problema es un ejemplo típico de esta categoría.
Laberintos y grafos en general. Englobamos aquí a todos los problemas que se plantean como laberintos y, en general, los que desde su enunciado nos proponen manejar un grafo. Los laberintos suelen ser fácilmente modelables como un grafo en el que las intersecciones (o habitaciones) son los nodos del grafo y la conectividad/accesibilidad entre unas y otras pueden ser modeladas mediante los arcos de dicho grafo. Estos arcos pueden ser dirigidos o no, dependiendo del tipo de problema que se plantee.
Este problema es un ejemplo típico de esta categoría.
Problemas matemáticos. Llamamos problemas matemáticos a aquellos problemas cuyo paso fundamental para su resolución es la obtención de un modelo matemático del problema, y que una vez bien planteado este modelo suele ser relativamente sencilla su resolución, al menos en términos conceptuales. A menudo este tipo de problemas se encuentran escondidos detras de planteamientos que intentan conducir al concursante hacia determinada técnica de diseño algorítmico que en la mayoría de los casos le suele llevar a rebasar el límite de tiempo máximo disponible en la ejecución.
Conviene estar alerta, tanto en este tipo de problemas como en todos los demás, para no dejarnos arrastrar por lo que parece evidente como método de resolución a la vista del enunciado.
Este problema es un ejemplo típico de esta categoría.
Vamos ahora a realizar una clasificación diferente de los problemas. Los clasificaremos según el tipo de algoritmo que los resuelve. Es importante distinguir ambas cosas, pues en ocasiones un algoritmo que está planteado aparentemente como un problema de un determinado tipo, puede ser resuelto de forma mucho más conveniente (y a menudo como única solución viable dentro de las restricciones dadas) de otra forma que aparentemente no tiene nada que ver con su planteamiento.
No es propósito de esta exposición introductoria dar una explicación exhaustiva de cada una de estas categorías, pues ello requeriría una extensión considerablemente superior a este documento (aparte de que las más notables de ellas serán objeto de estudio particular en sesiones posteriores), sino más bien bosquejar un panorama global de cuáles son los recursos más frecuentes con que cuenta un programador para enfrentarse con éxito a un concurso de programación.
Algoritmos ad-hoc. Se trata de algoritmos que no encajan en una técnica general de diseño. Con relativa frecuencia encontramos problemas que requieren la implementación de un algoritmo específicamente diseñado para su resolución.
Aunque debemos tenerlo en cuenta y dejar esta posibilidad abierta en todo momento, conviene echar mano de ella siempre como último recurso, ya que por lo general encontraremos problemas que serán resolubles mediante alguna técnica general de diseño.
Este problema se resuelve mediante un algoritmo de cálculo específicamente diseñado para este propósito.
Algoritmos de avance rápido. Los conocidos algoritmos voraces (greedy). Se basan en la realización de cálculos que aproximen al máximo a la solución del problema. Son útiles sobre todo cuando las características del problema hacen que este tipo de cálculos no provoquen el alcance de un estado a partir del cual no sea posible continuar hasta la solución total y sea necesario deshacer los cálculos realizados o parte de ellos.
Este problema se resuelve mediante un algoritmo de avance rápido.
Algoritmos con retroceso. Los típicos algoritmos de exploración del árbol de posibles soluciones (backtracking). Estos algoritmos tienen la ventaja de realizar una búsqueda exhaustiva de la solución, aunque presentan el inconveniente de ser en general altamente ineficientes. Existen variantes que pueden afinar más la búsqueda en función de los valores de la solución parcial que se vaya obteniendo para descartar a priori determinadas ramas del árbol de soluciones explorado (backtracking informado, o técnicas de ramificación y acotamiento).
En general no suele ser una buena idea lanzarse a la resolución de un problema mediante la técnica de retroceso sin antes considerar otras alternativas. En todo caso, y a la vista de los datos del problema, suele ser útil la realización de una estimación pesimista/optimista del tamaño del árbol que se va a explorar en la resolución de un caso de prueba típico, pues en determinadas ocasiones este cálculo sencillo, en el que podemos invertir un minuto, puede ser suficiente para descartar de entrada esta técnica por ser computacionalmente ruinosa para el caso bajo estudio.
Este problema se resuelve mediante un algoritmo de retroceso. Como puede comprobarse a la vista del enunciado, la pequeña cantidad de datos de entrada hace que el árbol de soluciones no sea excesivamente grande y, por tanto, un algoritmo con retroceso pueda funcionar aceptablemente bien en este caso [NOTA: hay un error en la descripción de la salida de este problema. Como puede observarse, solo está la salida para el primero de los casos de la entrada, y además falta el indicador de final <- tras el resultado de la última operación].
Algoritmos directos. Se trata de algoritmos que básicamente hacen una serie de cálculos que resuelven el problema de forma directa con independencia de lo que aparentemente es la entrada. A menudo, problemas que parecen sugerir soluciones complejas mediante algoritmos computacionalmente costosos pueden ser resueltos mediante uno de estos algoritmos si caemos en la cuenta de cuál es la relación directa que liga datos con resultados.
Este problema en realidad se resuelve mediante un cálculo directo en O(1), cuando intenta dar la engañosa apariencia de requerir algoritmos de exploración de árboles de decisión.
Algoritmos matemáticos. Englobamos en esta categoría los algoritmos que requieren la obtención de un modelo matemático subyacente para la correcta resolución del problema asociado, o bien la extracción de ciertas propiedades matemáticas que simplifiquen el problema.
Un ejemplo típico de este tipo de problemas es el siguiente: a veces nos encontramos con que necesitamos manejar números de tamaño enorme, del orden de 10100 o incluso de 101000. Obviamente, a día de hoy no disponemos de tipos de datos escalares que permitan representar estas magnitudes. La alternativa de programar estructuras de datos complejas para representarlos, o utilizar las de las librerías estándar del lenguaje empleado, con frecuencia suele conducir a no resolver el problema por un exceso de tiempo de ejecución (no olvidemos que con esos números tan grandes luego tendremos que hacer operaciones de complejidad igualmente grande) y también a no resolver ningún otro, tal es el esfuerzo y el tiempo invertido en seguir este camino hacia ninguna parte. En la práctica totalidad de los problemas de este tipo la solución pasa por descubrir ciertas propiedades numéricas del resultado buscado que hacen que no tengamos necesidad de almacenar el número completo, sino que podemos ir calculando la propiedad buscada conforme vamos leyendo dígitos o bloques de dígitos del número de la entrada.
Este problema se resuelve mediante un estudio de este tipo. Nótese que aunque la entrada en este caso es una línea de texto, en realidad se trabaja con un número subyacente compuesto por la concatenación de los códigos de representación interna de los caracteres que componen la línea. Además, este número es arbitrariamente grande, pues en ningún punto del enunciado se nos dice que exista una cota superior del número de caracteres que componen un mensaje.
Algoritmos por ordenación. Se trata de algoritmos cuya principal tarea descansa sobre el hecho de reorganizar de alguna manera los datos de la entrada para obtener la salida deseada.
Este problema básicamente se resuelve mediante la aplicación de un algoritmo de clasificación seguido de otros tratamientos menos relevantes relacionados con el formateo por columnas de los datos de salida.
Tratamiento de grafos. Incluimos en esta categoría a los algoritmos que tratan de alguna manera datos del problema modelados mediante un grafo. Los algoritmos típicos sobre grafos suelen estar relacionados con la obtención de una ordenación topológica de un grafo dirigido, obtención de caminos más cortos o de coste mínimo en grafos dirigidos o no, alcanzabilidad y/o componentes conexas, etcétera.
Con frecuencia sucede que un algoritmo elemental de manipulación de grafos resuelve un problema que a primera vista no tiene nada que ver con ellos. Este problema es un ejemplo de ello.
Recorridos lineales. Se trata de algoritmos que básicamente realizan un recorrido lineal de los datos de entrada, normalmente cadenas de caracteres o números largos tratados como cadenas. Son algoritmos relativamente eficientes, pues invierten un tiempo en O(n), y sencillos de codificar.
Este problema se resuelve mediante un sencillo recorrido lineal de la cadena de entrada.
Programación dinámica. La programación dinámica es una conocida técnica de diseño de algoritmos que puede ser utilizada con ventaja para la resolución de problemas que por lo general involucran ecuaciones de recurrencia cuya resolución mediante su expresión matemática elemental resultaría computacionalmente ruinosa. Estos algoritmos se apoyan en un array para evitar la repetición de un mismo cálculo más de una vez. Este array suele ser bidimensional, aunque en según qué casos y dependiendo de la forma de la recursión original puede simplificarse y reducirse a unidimensional.
El hecho de utilizar arrays para la resolución de un problema mediante un algoritmo basado en programación dinámica sugiere inmediatamente que necesitamos conocer a priori una cota superior del tamaño de los valores de entrada para los cuales debemos realizar los cálculos, y que esta cota debe ser razonable para poder diseñar a partir de ella el array en que se apoya esta técnica. En ocasiones, es posible "contraer" de alguna manera el dominio de los datos de entrada para utilizar un array de un tamaño más asequible.
Este problema se resuelve mediante un algoritmo de programación dinámica que combina muchas de las consideraciones anteriores.
Cualquier algoritmo maneja datos de algún tipo. Vamos a enumerar a continuación las estructuras que con más frecuencia nos serán necesarias para abordar estos problemas.
Ninguna. Determinados algoritmos resuelven el problema simplemente mediante el manejo de determinadas variables que de forma sencilla modelan el problema sin constituir estructura alguna de datos.
Arrays. El array es sin duda la estructura más popular y más utilizada en la mayoría de problemas. Es fácil de manejar, sus operaciones son muy eficientes y es posible modelar con él otras estructuras más complejas (por ejemplo, los grafos modelados mediante matrices de adyacencia). Mención especial dentro de esta categoría son los tipos que ofrecen las librerías estándar de los lenguajes para almacenar y manipular cadenas de caracteres. Estos tipos ofrecen alternativas muy útiles para el procesado de determinadas entradas, siempre que las cotas de tamaño dadas por el problema encajen con la especificación del tipo en el lenguaje elegido.
Otras estructuras lineales. Englobamos aquí las listas, colas, pilas y otros contenedores que ofrecen los lenguajes de programación, tales como los mapas, vectores y tablas. Conviene conocer la forma en que estas estructuras se pueden utilizar en alguno de los lenguajes que las ofrecen dentro de su librería estándar.
Estructuras no lineales. Los árboles y grafos son también utilizados con relativa frecuencia. Conviene conocer de antemano los tipos de árboles y grafos más frecuentes y la forma más conveniente de representarlos, así como los contenedores que los lenguajes ofrecen para proporcionarlos. En el caso concreto de los grafos, es especialmente relevante la elección de su forma de representación, pues dependiendo del problema puede ser interesante representarlos mediante arrays que contengan matrices de adyacencia (en el caso de pocos nodos y/o gran número de arcos) o representando los arcos mediante nodos de listas u otro tipo de estructuras (en el caso de un elevado número de nodos y escaso número de arcos).
En general, siempre que se usan los tipos contenedores que nos ofrecen las librerías de los lenguajes no debemos perder de vista que una operación que se realice sobre una de estas variables no necesariamente va a tener un coste en O(1), aunque para nosotros no suponga más que una línea de código.
Terminamos esta introducción general a los tipos de problemas y a su resolución con una serie de recomendaciones generales que confiamos sean útiles para el concursante:
Conoce esquemas algorítmicos. Es interesante conocer los esquemas algorítmicos que resuelven los problemas más comunes que hemos enumerado aquí. Esto nos puede ahorrar un tiempo precioso que podemos dedicar a los detalles del problema concreto, en lugar de dedicarlo a ``inventar la cuchara'' cada vez que nos sentamos a comer.
Escribe algoritmos sencillos. Si el algoritmo se nos complica excesivamente, tanto en lo que a estructuras de datos como a tratamientos se refiere, lo más probable es que vayamos directamente a un hoyo sin salida. Los algoritmos que se proponen en los concursos están pensados para ser resueltos con mucho ingenio y (generalmente) poco esfuerzo de codificación ni detalles de programación elevados.
Distingue entre problema y algoritmo. Haremos énfasis una vez más en que no existe necesariamente una correlación entre enunciado del problema y algoritmo que lo resuelve. Un enunciado que aparenta una cosa a menudo se resuelve mediante un algoritmo que nada tiene que ver con ello.
Piensa primero, escribe después. A menos que seas capaz de visualizar inmediatamente en tu mente la solución global del problema y no tengas duda sobre su corrección y eficiencia, no es una buena idea ponerse a escribir el programa inmediatamente después de leer el enunciado del problema. El tiempo que no se invierte en teclear el programa no necesariamente es tiempo perdido. De hecho, el tiempo dedicado a pensar antes de escribir a menudo ahorra muchísimo tiempo.
Lleva artillería preparada. Date cuenta de que hay ciertos tratamientos que son comunes en todos los problemas. Por ejemplo, la entrada de los problemas suele ser de ciertas formas comunes (enteros, reales, cadenas de caracteres; en líneas independientes o mezclados en la misma línea separados por blancos/tabuladores, etcétera). Una buena idea puede ser llevar preparadas las rutinas de entrada para tomar los datos correctamente utilizando el lenguaje elegido. Lo mismo se aplica para la salida. Para escribir números por la salida en determinada forma, enteros o reales, es interesante conocer de antemano los recursos que nos ofrece el lenguaje elegido. De este modo evitarás perder el tiempo en este tipo de detalles que realmente no aportan nada a la resolución del problema pero son ciertamente muy necesarios en todo caso.
Evita errores de redondeo. Utiliza aritmética entera siempre que puedas. El tipo de números reales en coma flotante no es el conjunto de los reales matemáticos. Sus propiedades son muy diferentes y la exactitud de los cálculos es una de las más relevantes diferencias. Si puedes, evita cálculos con números reales que requieran una precisión elevada (tolerancia 0.0 entre el valor calculado y el correcto).
Haz pruebas con valores significativos. Utiliza valores extremos para hacer las pruebas de tu programa. Algunos ridículamente grandes, otros ridículamente pequeños, respetando siempre las restricciones del enunciado. Cadenas de caracteres de longitud máxima y de longitud uno (o incluso cero, si es posible que se dé el caso). Haz que los casos que utilices para la validación de tu programa sean sencillos de diseñar y al mismo tiempo extremos.
Para concluir, en la siguiente figura resumimos de forma esquemática el proceso de resolución de un problema de concurso de programación:
Olimpiada de programación - Facultad de Informática - Universidad de Murcia