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