3330 - Hades and the Number of the Witch

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?pid=3330

[isaac]

Este ejercicio puede ser resuelto por varias formas, para mi entender la mas rapida y efectiva es usando programacion dinamica. Voy a poner un ejemplo que se parece bastante y que puede ser util ya que es una idea bastante similar. Supongamos que queremos buscar cuantas veces aparece en una cadena los caracteres 'a' y 'b' en ese orden. Podemos realizar dos contadores que cuenten la cantidad de caracteres 'a' y 'b' respectivamente. La primera idea sería imprimir el producto de estos dos contadores, pero en el caso de esta cadena "bbbbbbaaaaaa" la respuesta deberia ser cero y utilizando la multiplicacion vemos que no es esa la respuesta. Entonces, hacemos igualmente dos contadores(CA=0, CB=0). Si encontramos una 'a' ==> CA++ y si encontramos una 'b' ==> CB += CA, que seria la cantidad de formas en que, tomando la cantidad de caracteres 'a' previamente, puedo formar "ab" con la letra 'b' encontrada. Cuando se trata de un patrón de más de una letra, para la primera letra lo hacemos como una tabla acumulativa, pero el resto de las letras, tenemos que aumentar no solo en la cantidad de subcadenas tales que agregandoles ese caracter me contribuyan a la solucion, sino la cantidad de subcadenas ya formadas previamente. Por ejemplo:

Si tenemos el patrón que comienza con 53.......... y tenemos que la cadena en la que vamos a buscar es 50343....., entonces cuando encontremos un 5, simplemente aumentamos la cantidad de subcadenas "5" en 1, pero cuando vamos al 3, tenemos que aumentar la cantidad de subcadenas "53" en la cantidad de subcadenas "5" (porque al agregarles el ´3´ analizado se convierte en una de ellas) y tenemos que agregarle también la cantidad de subcadenas "53" encontradas hasta la posicion anterior, o sea en el caso del segundo ´3´ de mi ejemplo, tendriamos que sumar la cantidad de subcadenas "5" encontradas (que sería 1) y la cantidad de subcadenas "53" encontradas hasta la posicion anterior (correspondiente al caracter ´4´ que sería 1) por lo que tenemos para ese caso que es igual a 2. Asi sucesivamente con los restantes digitos. La complejidad sería O(LP * LT) donde LP y LP son las longitudes del patrón y el texto respectivamente.