Videos de GCJ10 Round 1C y TCO10 Qual 3

Esta semana he estado probando un programa para grabar la pantalla mientras programo las soluciones para problemas en competencias de programación. Aquí hay algunos de los resultados que he obtenido después de probar este software de grabación.

Esta semana he estado probando un programa para grabar la pantalla mientras programo las soluciones para problemas en competencias de programación. Primero, grabé las soluciones para la Ronda 1C del Google Code Jam (hice la competencia como práctica, ya que avancé en la Ronda 1A), e hice un video para el problema A - Rope Intranet.

Video para el problema A de la Ronda 1C del Google Code Jam 2010, Rope Intranet.

Este problema es fácil de resolver, iterar sobre cada par de cuerdas chequeando si éstas se intersectan es suficiente para tener el problema aceptado. Como pueden ver en el video, mi único error fue leyendo los datos de entrada; esto pasó porque lei el enunciado del problema por encima. Todavía tengo la grabación de los otros dos problemas, pero aun no los he post-procesado.

Después, grabé mis soluciones para los problemas de la 3ra ronda de clasificación del TopCoder Open 2010. De nuevo, las hice como práctica, ya que avancé a la Ronda 1 utilizando un comodín (Bye). El primer video que creé fue para el problema fácil, SumRectangle. Para este video, mejoré el manejo del zoom y la calidad, corté las partes donde leo el enunciado (añadiendo un indicador amarillo con el tiempo transcurrido), y añadí una firma en la esquina inferior-derecha.

Video para el problema fácil de la 3ra ronda clasificatoria del TopCoder Open 2010, SumRectangle.

Este problema es sencillo, sólo hace falta calcular los valores faltantes dentro de la matriz utilizando aquellos que ya se encuentran calculados. Sin embargo, hay que tener cuidado con el enunciado, ya que éste dice que la respuesta final podría no ser única. No obstante, después de un análisis sencillo se puede deducir que la respuesta siempre existe y es única, dados leftColumn y topRow.

También creé un video para problema medio, llamado WhatsThisChord. Este problema puede ser resuelto por una simulación directa, después de observar que las notas se pueden convertir a enteros entre 0 y 12, inclusive, implementando la adición en módulo 13.

Video para el problema medio de la 3ra ronda clasificatoria del TopCoder Open 2010, WhatsThisChord.

Aquí hay algunas características del ambiente que utilizo para programar para las competencias de programación:

• Utilizo Windows 7 Profesional de 64 bits como sistema operativo y Visual Studio 2010 como entorno de desarrollo. También tengo Linux, pero utilizo Visual Studio para trabajar y mi AddIn sólo funciona ahi.


• Tengo una HP DV7-3188CL, con una pantalla de 17'' 16:9, un procesador Intel Core i5 de 2.5Ghz, 6GB de memoria RAM DDR3 y una tarjeta de video NVIDIA GeForce G105M. Además, tengo un ratón externo Logitech G5, un teclado en inglés HP externo y un monitor de alta definición de 26''.


• Utilizando el monitor de alta definición y la pantalla de la computadora portátil, tengo un área de trabajo de 1920x1200 + 1600x900 píxeles, los cuales divido verticalmente en cuatro ventanas (dos por cada pantalla). De esta forma, puedo ver el enunciado del problema, el código fuente y la tabla de puntuación actual al mismo tiempo.


• Utilizo CodeProcessor 2, FileEdit y moj al resolver problemas en TopCoder. De esta forma, un archivo fuente con una plantilla básica (nada especial, sólo #includes y el esqueleto de la clase) y funciones de prueba son generadas automáticamente en cuanto abro el problema. De esta forma, puedo programar en mi IDE favorito y puedo probar todos los casos de prueba en una sola corrida.


• Utilizo un AddIn personal para Visual Studio, el cual expande macros de código parametrizables mientras programo. Implementé este AddIn utilizando C++/CLI para interactuar con el IDE y Boost.Spirit para interpretar las definiciones de macros. De esta forma, puedo escribir de forma rápida y confortable como si utilizara #defines, pero sin el código ilegible que éstas dejan.

Área de trabajo con computadora portátil, teclado, ratón y monitor externo y Wii.

Espero que le hayan gustado los videos, voy a tratar de hacerlos y subirlos tanto como pueda. Probablemente, en otra publicación, hable más sobre mi ambiente de programación y el AddIn (el cual se llama TopCoderAddIn).

Leer más...

Torneos de Programación Mundiales - (GCJ|TCO)10

Desde el 2008, hay dos competencias de programación a nivel mundial donde casi cualquiera puede participar. Este año no es la excepción, ya que se acercan las fechas del TopCoder Open 2010 y del Google Code Jam 2010.

Desde el 2008, hay dos competencias de programación a nivel mundial donde casi cualquiera puede participar. Este año no es la excepción, ya que se acercan las fechas del TopCoder Open 2010 y del Google Code Jam 2010.

El TopCoder Open es organizado por TopCoder anualmente, y este año tiene varias competencias donde los programadores pueden participar: Algoritmos, Diseño, Desarrollo, Maratón, Mod Dash y Estudio. Este año participaré únicamente en las competencias algorítmicas, ya que no tengo experiencia alguna en las otras competencias.

El TopCoder Open 2010 (ver calendario aquí) estará dividido en tres rondas clasificatorias, cinco rondas en linea y las finales presenciales en Las Vegas, Estados Unidos. Para clasificar a las finales, se debe estar en los primeros 600 lugares en cualquier ronda clasificatoria y pasar las cinco rondas en linea. Para este año, estoy practicando para avanzar al menos a la ronda 5 y así obtener una oportunidad de clasificar a las finales. Franelas del TCO10 serán otorgadas a las 350 personas que clasifiquen a la ronda 3.

El Google Code Jam es organizado por Google anualmente desde el 2008 (anteriormente era organizado por TopCoder), y sólo contiene problemas algorítmicos, no hay problemas de diseño o desarrollo como en el TCO. Este torneo difiere con los demás debido a que son orientados a los datos, es decir, el usuario descarga un archivo de entrada y envía el archivo de salida generado por su solución.

El Google Code Jam 2010 (ver calendario aquí) será dividido en una ronda clasificatoria de 24 horas, tres rondas en linea y las finales presenciales en Dublin, Irlanda. Para clasificar a las finales, se debe resolver un problema en la ronda clasificatoria y pasar las tres rondas en linea. Este año espero avanzar a la ronda 3 para obtener una oportunidad de avanzar a la final. Franelas del GCJ10 serán otorgadas a las 500 personas que avancen a la ronda 3.

Para completar este post, aquí hay unas fotos con todas las franelas que he ganado en competencias a nivel mundial. En la siguiente imagen podrán ver mis franelas de las finales mundiales del ACM-ICPC a las que he asistido.

De izquierda a derecha: 30va Final Mundial del ACM-ICPC, Texas, US; 31ra Final Mundial del ACM-ICPC, Tokyo, Japón; 32da Final Mundial del ACM-ICPC, Banff, Canadá.

Además, después de esas competencias Google nos invitó a São Paulo y Belo Horizonte, donde nos dieron las siguientes franelas:

De izquierda a derecha: 30va Final Mundial del ACM-ICPC, São Paulo, Brasil; 31ra Final Mundial del ACM-ICPC, Belo Horizonte, Brasil.

Esto fue lo que gané en el TopCoder Collegiate Challenge 2007 (TCCC 2007). También gané una botella de agua y una pelota anti-estrés, pero no las pude encontrar.

Franela y gorra del TopCoder Collegiate Challenge 2007.

Como verán en la siguiente imagen, poseo las franelas del GCJ06, GCJ08 y GCJ09, así que espero poder ganar la franela del GCJ10 para mantener mi colección completa.

De izquierda a derecha: Google Code Jam 2006 para empleados, Mountain View, CA, US; Google Code Jam 2008, New York, NY, US; Google Code Jam 2009.

A medida que pasen las rondas de estos torneos analizaré algunos problemas de éstas, subiendo los análisis lo más pronto posible. Buena suerte a todos aquellos que vayan a participar en estos torneos, nos vemos en la Arena.

Leer más...

SPOJ - 3407. Candy (SAMER08C)

El problema analizado hoy fue utilizado en el Regional Suramericano del 2008, donde fui el administrador del servidor y vi toda la acción desde adentro. Este problema puede ser resuelto utilizando Programación Dinámica, la cual es simple si el análisis se hace correctamente.

El problema analizado hoy fue utilizado en el Regional Suramericano del 2008, donde fui el administrador del servidor y vi toda la acción desde adentro. Hasta donde puedo recordar, sólo un equipo de Venezuela pudo resolver este problema durante la competencia, pero en SPOJ ha sido resuelto por más de 150 personas.

Enunciado del Problema

Este problema fue utilizado en el Regional Suramericano, pero Diego Satoba lo subió a SPOJ aqui. Sin embargo, no se si los casos de prueba utilizados son los mismos que fueron utilizados durante la competencia oficial.

Análisis del Problema

Este problema pide calcular la mayor cantidad de caramelos que se pueden tomar de la tabla, con la condición de que al tomar caramelos de una caja todas las cajas en las dos filas adyacentes y las dos cajas a los lados son vaciadas. Inicialmente el problema se ve complejo debido a que parece que el orden en que los caramelos son tomados importa; esto implica que se debe optimizar el orden en el que se toman los caramelos aparte de optimizar cuáles se deben tomar.

Las primeras dos propiedades a observar sobre la tabla son:

• Si al tomar una caja B1 se vacía una caja B2, entonces tomar la caja B2 ocasiona que se vacía la caja B1.
• Si al tomar una caja B1 no se vacía una caja B2, entonces tomar la caja B2 no ocasiona que se vacía la caja B1.

Este par de propiedas (y el hecho de que el operador de adición sobre los enteros es conmutativo) implica que el orden en que se tomen los caramelos no importa. Esto simplifica la solución, ya que se puede asumir que los caramelos se toman en un orden específico a nuestra conveniencia.

Otro aspecto complejo en el problema es que la tabla no se mantiene constante mientras se toman los caramelos, debido a que algunas cajas son vaciadas cuando algunos caramelos son tomados de otras cajas. Para simplificar esto es suficiente ver que vaciar una caja es equivalente a prevenir que se tomen caramelos de ésta. De esta forma, no es necesario modificar la tabla durante la ejecución del algoritmo.

Resolviendo un problema más simple

Ahora que el problema ha sido simplificado, es hora de ver como se puede obtener el máximo número de caramelos de la tabla. Primero, es mejor resolver un problema más simple para luego expandir la solución: dado un arreglo de caramelos, calcular el máximo número de ellos que se pueden tomar, si al tomar caramelos de una caja vacía las dos cajas adyacentes. Esto es equivalente a optimizar una fila en el problema original.

Para obtener el mayor número de caramelos posibles de una fila, se puede utilizar el hecho de que el orden en que se toman no importa para asumir que estos se toman de izquierda a derecha. Ahora que un orden ha sido establecido, la solución se puede formular utilizando Programación Dinámica (DP por sus siglas en inglés). Sea n el número de celdas en la fila, sea F_i el máximo número de caramelos que se pueden tomar si sólo las cajas i a la n-1 están disponibles, y sea C_i el número de caramelos en la caja i. La función F_i se puede plantear recursivamente de la siguiente manera:

F_i = \left\{
\begin{array}{ll}
  0 & \textrm{si $i \ge n$}\\
  \max(C_i + F_{i+2}, F_{i+1}) & \textrm{si $i < n$}
\end{array}\right

La definición recursiva de F_i funciona de la siguiente manera:

• El primer caso (i ≥ n) es el caso base, el cual ocurre cuando se desea obtener el máximo sobre una fila vacía. Como no hay caramelos para tomar, el valor de retorno debe ser 0.


• El segundo caso (i < n) es el único caso recursivo, el cual ocurre cuando aún quedan caramelos por tomar. En este punto existen dos opciones: tomar los caramelos y saltar la siguiente caja, o no tomar los caramelos y continuar con la siguiente caja. Entre esas dos opciones, se desea la que permita obtener la mayor cantidad posible de caramelos.

Implementar esta función de forma recursiva requiere tiempo de ejecución O(2^n), pero éste se puede reducir a O(n) utilizando DP (ver Implementación de la Solución para más detalles).

Extendiendo para el problema original

Una vez el problema ha sido resuelto para una fila, es hora de extender la solución para que funcione sobre toda la tabla. Si se observa de forma detenida el comportamiento de las filas en el problema, se puede ver que tomar un caramelo de una fila vacía completamente ambas filas adyacentes, y después de eso no hay otra forma de que se vacía esta fila. Con base en esto, se puede plantear una solución extendiendo F_i sobre una tabla, añadiendo una bandera para indicar si al menos un caramelo se tomo de la fila actual.

Desafortunadamente, esta solución es difícil de programar, ya que almacentar toda la tabla en un arreglo bidimensional excederá el límite de memoria (10^10 enteros requieren aproximadamente 9.3GB de memoria). Para almacenar toda la matriz al mismo tiempo, esta se debe almacenar en un arreglo unidimensional y su accesso se debe hacer de forma manual, en lugar de ser manejado por el compilador.

Para sobrepasar esta dificultad, es importante observar una vez se ha tomado un caramelo de una fila, la solución óptima implica tomar tantos caramelos como sea posible de esa fila. Esta propiedad permite la creación de una solución más simple: primero, se calcula el máximo número de caramelos que se pueden tomar de cada fila, y entonces (utilizando el mismo algoritmo) se calcula el conjunto óptimo de filas a tomar.

Utilizando esta reducción, la implementación de la solución debería ser corta y simple.

Implementación de la Solución

Como se mencionó en la sección anterior, la solución para optimizar filas se utilizará para optimizar toda la tabla, así que el primer paso lógico sería implementar la solución propuesta utilizando DP. En este problema, se utilizará un DP bottom-up, debido a que la versión top-down podría ocasionar un desbordamiento de pila. Primero, se debe declarar un arreglo para almacenar los valores calculados, añadiendo dos¹ posiciones adicionales para los casos de borde.

const int MAX_N = 100000;
int dp[MAX_N + 2];

Después de delcarar el arreglo, se debe implementar la función para optimizar un fila. Esta función debe recibir un apuntador a la fila y un entero con el tamaño de la misma, y debe operar de la siguiente manera:

• Inicializar los dos casos base con el valor de retorno 0.


• Procesar los estados comenzando desde los más pequeños hacia los más grandes, i.e.: desde n-1 hacia 0.


• Por cada estado, calcular el valor de F_i utilizando el caso recursivo. Los valores de F_{i+1} y F_{i+2} pueden ser tomandos directamente del arreglo, ya que los índices superiores ya han sido calculados.


• Después de procesar todos los casos, retornar el resultado de optimizar sobre toda la fila, i.e.: F_0.

int f(const int* c, int n) {
  dp[n] = dp[n + 1] = 0;
  for (int i = n - 1; i >= 0; --i)
    dp[i] = max(c[i] + dp[i + 2], dp[i + 1]);
  return dp[0];
}

Ahora se debe implementar la función principal, la cual consiste en un ciclo que lee y resuelve cada caso de prueba. Para resolver un caso, se declara un arreglo para almacenar el resultado de optimizar cada fila, que se puede llenar leyendo y optimizando fila por fila. Finalmente, se debe optimizar el arreglo con los óptimos de todas las filas utilizando la misma función, la cual retornará el valor óptimo para toda la matriz.

int main() {
  // zyx3d me dió la idea de utilizar (m | n | ...) != 0 para verificar el final.
  for (int m, n; scanf("%d %d", &m, &n) == 2 && (m | n) != 0;) {
    // Leer y optimizar cada fila, almacenando las respuestas en otra fila.
    static int rowOptimals[MAX_N];  // Resultados parciales de cada fila.
    for (int i = 0; i < m; ++i) {
      // Leer una fila, obtener el valor óptimo y almacenarlo.
      static int row[MAX_N];  // Arreglo con la fila actual.
      for (int j = 0; j < n; ++j) scanf("%d", &row[j]);
      rowOptimals[i] = f(row, n);
    }
    // Al final, optimizar las filas utilizando el mismo algoritmo.
    printf("%d\n", f(rowOptimals, m));
  }
  return 0;
}

Conclusión

En este artículo se presentó la solución para el problema SPOJ CANDY, utilizando una solución que lee y procesa una fila a la vez, y luego reutiliza el mismo algoritmo para resolver el problema para toda la matriz. Es importante resaltar que se implementó una solución simple e inteligente observando que el comportamiento de las filas en la matriz es el mismo comportamiento de las celdas en cada fila.

---

1. Si sólo se declara una posición extra, el arreglo será accesado por fuera cuando F_i necesite F_{i+2}, con i=n+1.

Leer más...

TopCoder - SRM 461 - Name Input

El problema NameInput fue utilizado en el SRM 461 de TopCoder como el problema difícil de la División 2, el cual puede ser resuelto utilizando el algoritmo de Dijkstra para conseguir el camino más corto en un grafo.

El problema NameInput fue utilizando en el SRM 461 de TopCoder como el problema difícil de la Division 2, el cual fue resuelto únicamente por 13 competidores de 1141. Este SRM fue posible gracias a dolphinigle, quien donó los cinco problemas gratuitamente.

Enunciado del Problema

[+/-] Mostrar/Ocultar enunciado del problema (inglés)

You want to input your name into your personal handheld. Your handheld has only one input method. This input method uses a sequence of characters to predict what character you might input next. The input proceeds according to keys pressed by the user:

• Initially, the handheld shows the first character in the prediction sequence.


• If the user presses the 'up' key, the handheld shows the next character in the sequence (or the first character in the sequence if it was showing the last character).


• If the user presses the 'down' key, it shows the preceeding character in the sequence (or the last character in the sequence if it was showing the first character).


• If the user presses the 'enter' key, then the character currently shown by the handheld is input (the character shown by the handheld remains the same).

Since you want to input your name, the i-th character input by the handheld must equal the i-th character of your name.

You are given String[] predictionSequence and String[] name. To obtain the prediction sequence of the input method concatenate all elements of predictionSequence. To obtain your name concatenate all elements of name. Return the minimum number of 'up' and 'down' keypresses that are necessary to input your entire name or -1 if it is impossible.

Notes

• Both your name and the prediction sequence are case sensitive, that is, 'B' is different from 'b' and 'd' is different from 'D'.

Constraints

• predictionSequence will contain between 1 and 50 elements, inclusive.


• Each element of predictionSequence will contain between 1 and 50 characters, inclusive.


• Each character in each element of predictionSequence will be a lowercase letter ('a'-'z'), an uppercase letter ('A'-'Z') or a digit ('0'-'9').


• name will contain between 1 and 50 elements, inclusive.


• Each element of name will contain between 1 and 50 characters, inclusive.


• Each character in each element of name will be a lowercase letter ('a'-'z'), an uppercase letter ('A'-'Z') or a digit ('0'-'9').

Examples

1. • Input: {"Jjhon"}, {"John"}
   • Returns: 5
   • Explanation: Press enter, down, down, enter, down, enter, up, up, enter. This will complete the name input process and use only 5 up and down keypresses.


2. • Input: {"abcdefghijklmnopqrstuvwxyz", "ABCDEFGHIJKLMNOPQRSTUVWXYZ", "0123456789"}, {"Joh", "nAndFr", "iends"}
   • Returns: 186
   • Explanation: To obtain the full prediction sequence concatenate all the elements of predictionSequence. To obtain the full name concatenate all the elements of name. This yields "JohnAndFriends".


3. • Input: {"aaaabbbab", "baabbabaabba"}, {"bbaaababba", "baababababbb"}
   • Returns: 16
   • Explanation: Multiple occurences of characters may be present in both parameters.


4. • Input: {"john"}, {"John"}
   • Returns: -1
   • Explanation: Since it is case sensitive it is impossible to input the letter 'J'.


5. • Input: {"4"}, {"4444444444444"}
   • Returns: 0
   • Explanation: Press enter 13 times.


6. • Input: {"abcABC123","cbaCBA321"}, {"aB32C2AaB3c","c32bA"}
   • Returns: 38

---

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2006, TopCoder, Inc. All rights reserved.

[+/-] Mostrar/Ocultar enunciado del problema (inglés)

Análisis del Problema

Este problema pide calcular el mínimo número de movimientos que debe realizar el cursor para escribir una cadena (name), donde éste se mueve circularmente sobre una secuencia de caracteres especificada como parámetro (predictionSequence). Una opción para resolver este problema es utilizar Programación Dinámica (DP por sus siglas en inglés) sobre la posición del cursor y el próximo caracter a escribir. Sin embargo, cuando se intenta utilizar esta solución existen dos opciones para representar las transiciones en el DP:

1. Definir tres posibles transiciones: mover el cursor hacia arriba, hacia abajo y escribir el caracter actual. No obstante, estas transiciones hacen la programación del DP cuesta arriba, ya que es posible ir de un estado a sí mismo (i.e.: existen ciclos), y no se recomienda el uso de DP cuando existen ciclos en las transiciones.


2. Hacer que todas las transiciones escriban al menos un caracter, de forma que no hayan ciclos en las transiciones. Para implementar esto, se debe intentar escribir cada caracter en la secuencia de predicción, moviendo el cursor y escribiéndolo si es el que se necesita. Esto funciona, pero esta solución no corre en tiempo ya que necesita tiempo O(n^3) (donde n es el tamaño máximo entre ambas cadenas), lo cual no es lo suficientemente rápido para cadenas con 2500 caracteres. Esta solución puede ser optimizada para intentar únicamente el primer caracter válido a la izquierda y a la derecha, pero eso es un poco más complicado que la solución esperada.

Otra opción es modelar el primer intento de DP como un grafo con un nodo por cada estado y una arista por cada transición entre ellos. Luego, se puede utilizar el algoritmo de Dijkstra para conseguir el camino más corto entre el estado inicial (no hay caracteres escritos y el cursor se encuentra al comienzo) hacia cualquier estado final (todos los caracteres escritos). Sin embargo, el grafo no tiene que ser representado de forma explícita, una representación implícita es suficiente cuando se implementa el algoritmo de Dijkstra.

Implementación de la Solución

La solución para este problema es sencilla si el algoritmo de Dijkstra se separa e implementa en diferentes partes por separado. Implementar Dijkstra utilizando estos simples pasos lo hace mucho más sencillo:

1. Definir una estructura para almacenar toda la información acerca de un estado en la cola, incluyendo el operador de comparación para la cola de prioridad. Una estructura con tres enteros es suficiente para este problema, pero existe un detalle con la cola de prioridad (priority_queue) en C++: ésta retorna el máximo elemento en lugar del mínimo, por lo cual se debe "engañar" al operador de comparación para que retorne el menor elemento.

   struct state_t {
     state_t(int i_, int j_, int cost_)
       : i(i_), j(j_), cost(cost_) {}
     bool operator <(const state_t& s) {
       return s.cost < cost;  // zyx3d me enseñó este truco.
     }
     int i;     // Posición del cursor dentro de la secuencia de predicción.
     int j;     // Posición del siguiente caracter a escribir.
     int cost;  // Costo acumulado de este estado en la cola.
   };
   



2. Definir un arreglo para almacenar el costo mínimo encontrado por cada nodo, y un valor a utilizar como infinito. Este valor infinito debe ser lo suficientemente grande de forma que se pueda diferenciar de valores finitos, y también debe ser lo suficiente pequeño de forma que sumar dos de ellos no cause un overflow. El valor 0x3f3f3f3f es bueno, debido a que el doble de éste cabe en un entero de 32 bits y se puede utilizar la función memset de C++ para inicializar el arreglo.

   const int INFINITE = 0x3f3f3f3f;  // Buen valor para memset().
   int minCost[2500][2501];          // Indexado por [state_t::i][state_t::j].
   



3. Definir una función para añadir un nuevo estado a la cola. Esta función debe hacer todas las validaciones y, si el estado es válido y el costo es menor el que mejor encontrado, añadir un nuevo estado a la cola, actualizando el menor costo encontrado.

   void AddToFringe(priority_queue<state_t>& fringe, int i, int j, int cost) {
     if (cost < minCost[i][j]) {
       minCost[i][j] = cost;
       fringe.push(state_t(i, j, cost));
     }
   }
   



4. Finalmente, implementar la función principal del algoritmo de Dijkstra utilizando las estructuras y funciones definidas previamente. El algoritmo consta de dos partes principales: la inicialización y el ciclo de procesamiento. Durante la inicialización, el arreglo con los costos mínimos se inicializa con infinito, se define la cola y se insertan los estados iniciales en esta. En el ciclo de procesamiento, se toman un estado de la cola y se verifica si es el estado final, y luego se procesa cada una de las transiciones saliendo de éste.

   int Dijkstra(const string& seq, const string& st) {
     const int n = (int)seq.size(), m = (int)st.size();
     memset(minCost, INFINITE, sizeof(minCost));
     priority_queue<state_t> fringe;
     for (AddToFringe(fringe, 0, 0, 0); !fringe.empty();) {
       // Tomar el siguiente estado, verificar si uno mejor ya fue procesado
       // o si es el estado final.
       const state_t s = fringe.top(); fringe.pop();
       if (s.cost > minCost[s.i][s.j]) continue;
       if (s.j >= m) return s.cost;
   
       // Seguir las tres transiciones que salen del estado actual:
       // 1. Escribir el caracter actual.
       // 2. Mover el cursor a la izquierda.
       // 3. Mover el cursor a la derecha.
       if (seq[s.i] == st[s.j]) AddToFringe(fringe, s.i, s.j + 1, s.cost);  // (1)
       AddToFringe(fringe, (n + s.i - 1) % n, s.j, s.cost + 1);             // (2)
       AddToFringe(fringe, (n + s.i + 1) % n, s.j, s.cost + 1);             // (3)
     }
     return -1;  // Retornar un valor especial en caso de no encontrar el camino.
   }
   

   Es importante tomar en cuenta la línea 9, o la solución podría exceder el tiempo límite si no se ignoran los estados ya procesados en grafos densos (i.e.: grafos con muchas aristas).

Después de implementar Dijkstra, lo único que falta es construir las cadenas e invocar la función, lo cual se puede realizar utilizando la función accumulate de la STL.

struct NameInput {
  int countUpDownKeyPresses(vector<string> predSeq, vector<string> name) {
    const string seq = accumulate(predSeq.begin(), predSeq.end(), string());
    const string st = accumulate(name.begin(), name.end(), string());
    return Dijkstra(seq, st);
  }
};

Conclusión

Reconocer que el problema se puede resolver utilizando el algoritmo de Dijkstra en lugar de Programación Dinámica puede ser difícil si no se ha visto la implementación de Dijkstra sobre un grafo implícito. Después de eso, definir los estados y las transiciones entre estos es sencillo, y la implementación es simple si se hace paso por paso.

Problemas Similares

A continuación se encuentra una lista de problemas que pueden ser resueltos utilizando Dijkstra sobre un grafo implícto. Se recomienda resolverlos si el lector desea mejorar la implementación y el uso de este algoritmo.

• SPOJ - Deliver Pizza
• SPOJ - Bomb the Bridge
• SPOJ - Words on Graphs
• SPOJ - Laser Phones
• SPOJ - Ones and Zeros

Leer más...

Reglas para los comentarios

Un punto importante a considerar durante la configuración del blog son los comentarios. Básicamente, hay dos opciones: no permitir comentarios o permitirlos y moderarlos. A continuación algunas reglas básicas para los comentarios, de forma que todo se mantenga en un ambiente amigable.

Una decisión que se debe considerar durante la configuración del blog es si los comentarios son permitidos o no. Básicamente hay dos opciones: no permitir comentarios o permitirlos y moderarlos. La primera opción facilita la gestión del blog a cambio de menor interacción con los usuarios. Debido a esto elegí la segunda opción, que requiere algo de mi tiempo para revisar y moderar los comentarios, así que el primer paso es establecer reglas básicas para estos:

• No están permitidos los insultos, mensajes ofensivos o spam. Cualquier contenido de este tipo no será tolerado.


• No comentar sobre tópicos no relacionados con el artículo donde se está comentando. Revisen los comentarios anteriores a ver si su duda ya fue mencionado anteriormente.


• No preguntar a otros para que hagan sus tareas, el propósito de una tarea es resolverla uno mismo, aprender y mejorar, no obtener una calificación.


• No preguntar por código completo. Los demás programadores invierten su tiempo estudiando y practicando para mejorar sus habilidades, preguntar por código sólo demuestra flojera. Es mucho mejor discutir las soluciones y tratar de encontrar errores en la lógica de estas.


• No publicar código fuente esperando que otros encuentren los errores, depurar código consume bastante tiempo. Hay otros lugares mejores para esto, como el foro de TopCoder o el foro específico del juez en línea (la mayoría de estos proveen una).


• Los comentarios sólo se permiten en español.


• Si van a colocar enlaces, siempre traten de enlazar lugares seguros, como Wikipedia, Mathworld, PlanetMath, entre otros. Comentarios a lugares inseguros serán eliminados.


• Se recomienda el uso de las reglas de ortografía y gramática, así como evitar el uso de abreviaciones innecesarias. Si un comentario contiene demasiado abuso del español será eliminado automáticamente.


• Si se va a criticar algo, es mejor que sea una crítica constructiva con una solución incluida, en lugar de una crítica destructiva cuyo único propósito es descalificar al otro.


• Estan totalmente prohibídos los comentarios con tinte político o religioso.

Por supuesto, existía una tercera opción; permitir los comentarios sin moderación. Realmente lo pensé, porque la moderación requerirá parte de mi atención. Si veo que no puedo manejar la carga apagaré la moderación y veré cómo va todo.

Además, he activado el sistema de evaluación y encuestas rápidas para cada artículo. Por favor úsenlos, sólo toma un par de segundos y me da información invaluable sobre el contenido. ¿Es el artículo bueno? Evalúenlo. ¿Es el artículo malo? Evalúenlo y comenten porque no les gustó, a lo mejor el problema es aburrido o cometí un error en algún lugar, pero me gustaría saber de forma que pueda mejorarlo.

Estas reglas pueden cambiar con el tiempo, pero cualquier cambio será informado.

Leer más...

Bienvenida e Introducción

Hola lectores, bienvenidos a mi blog sobre análisis de problemas de programación en jueces en línea. Aquí analizaré problemas de diversos jueces en línea y sus respectivas soluciones, desde problemas simples hasta problemas geométricos, pasando por Programación Dinámica. En este artículo se describirán los jueces en línea que he utilizando así como información básica acerca de este blog.

Hola lectores, bienvenidos a mi blog sobre análisis de problemas de programación en jueces en línea. Aquí se analizarán problemas de diversos jueces en línea y sus respectivas soluciones, desde problemas simples hasta problemas geométricos, pasando por Programación Dinámica. En este blog principalmente se analizarán problemas de TopCoder, SPOJ y del Google CodeJam. Sin embargo, también he trabajado con otros jueces por algún tiempo; a continuación se mostrará una lista describiéndolos, incluyendo enlaces a estos:

• TopCoder: Los problemas de las competencias algorítmicas (Algorithm Track) son buenos para conseguir una mayor velocidad y precisión a la hora de resolver problemas, los cuales están clasificados por división y dificultad. Además, la arena permite probar las soluciones, ver en que casos fallaron y sus respuestas correctas, lo cual es muy útil para aprender. TopCoder además proveé competencias más largas (Marathon Matches), los cuales contienen problemas mucho más complicados cuyo propósito es conseguir la solución más aproximada posible, debido a que la solución exacta es imposible de obtener en el tiempo estipulado.


• Sphere Online Judge: Este juez en línea provee dos tipos de problemas: clásicos (Classic) y retos (Challenge). Las soluciones a los problemas clásicos o están correctas o incorrectas, mientras que los retos son evaluados utilizando alguna métrica, como el número de respuestas correctas o la longitud del código fuente. Además, los problemas generalmente están bien estructurados, el sistema es rápido y soporta diversos lenguajes de programación, incluyendo lenguajes esotéricos como Intercal, Brainfuck y Whitespace.


• Google CodeJam: En el 2008, Google realizó una nueva competencia de programación llamada el Google CodeJam, la cual funciona con un nuevo sistema que mezcla características de la IOI, el ICPC y TopCoder, e incluye varios problemas interesantes. Logré llegar a las semifinales realizadas en New York en el 2008, y logré llegar a la 3ra ronda en el 2009 (mi nombre de usuario es jbernadas, pueden ver mis resultados y mis soluciones en el scoreboard si lo desean).


• UVa Online Judge: Trabajé en este juez por tres años, pero lo abandoné a favor de SPOJ después de que "actualizaron" su sistema. Parece que ya tienen el nuevo servidor, así que debería revisar este juez con más frecuencia.


• CII Live Archive: Este juez tiene problemas de maratones regionales y mundiales previos de la ICPC, el sistema es rápido pero sus soporte para Java es malo (Java v1.1). Sin embargo, esto nunca me ha afectado debido a que utilizo C++ principalmente.

La idea de este blog es analizar problemas en estos jueces y dar algunas pistas y código fuente. Todo el código fuente en este blog estará escrito en C++ al comienzo y por algo de tiempo, ya que es el lenguaje que más he utilizado (por más de cinco años). También sé Java pero no lo utilizo mucho para las competencias, y actualmente estoy aprendiendo Python.

Trataré en la medida de lo posible actualizar este blog regularmente, publicando un análisis al menos una vez por semana, y si consigo más tiempo libre podría publicar con más frecuencia. También revisen los enlaces en la columna, ahí hay enlaces a herramientas creadas por otros programadores que pueden resultar útiles para buscar problemas por tópicos o probar sus soluciones.

Leer más...