3102 - Word Equations

[ymondelo20]

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

[jose92]

Me parece que hay un bug a la hora de juzgar este problema,me esta dando memoria limite excedida habiendo utilizado muy pocas variables teniendo en cuenta que el limite es de 62MB, ademas he utilizado mucha más memoria en otros problemas con el mismo limite obteniendo aceptado.Por favor diganme si me equivoco o si realmente es un bug arreglenlo y rejuzgen.

[humbertodiaz]

No estoy seguro si existe un problema con el juez ahora mismo, pero podria verificar tu codigo si lo pones aqui temporeramente. O me lo puedes enviar por un mensaje privado aqui. Ya yo resolvi ese ejercicio.

Edit: Verifique el codigo de Jose. Creo que construye una cadena de largo exponencial que excede los limites de memoria.

[Dariel]

Puedes explicar la idea de como resolver este ejercicio??

[humbertodiaz]

Primero, como no se puede resolver el ejercicio. No puedes tratar de construir la cadena que especifican a traves de los datos. La expansion de una variable puede crear una cadena de tamaño exponencial. Cada variable se puede usar para duplicar el tamaño de otra, y si se aplica eso multiples veces, el resultado es una cadena enorme. Potencialmente de 5 * 2^499 = 8.18 * 10^150 letras.

Esto es un ejemplo de como hacerlo:

A = B + B
B = C + C
C = D + D
D = E + E
E = F + F
F = abcde

El objetivo aqui es determinar si el patron (P en las instrucciones) es una subsecuencia de la expansion de un simbolo inicial determinado. Podemos formar una tabla F[x][k] donde guardamos la cantidad de caracteres de P que se encuentran en el simbolo x comenzando en el indice k en P. Por ejemplo, vamos a ver como se llena la tabla cuando P = "debate" y estamos mirando un simbolo X = "bad".

F[X][0] = 1
debate bad
F[X][1] = 0
debate bad
F[X][2] = 2
debate bad
F[X][3] = 1
debate bad
F[X][4] = 0
debate bad
F[X][5] = 0
debate bad

Se pueden asociar los simbolos con numeros para simplificar la implementacion en algunos lenguajes.

Existen dos casos para llenar la tabla. Considera los simbolos que estan atados directamente a palabras. Todos los demas simbolos siempre dependen de ellos eventualmente. La fila en la tabla para tal simbolo se puede llenar en tiempo O(P) debido a que podemos examinar cuantos caracteres de P aparecen comenzando desde todos los indices k. Esto pareceria tomar tiempo cuadratico en el largo de la palabra por el tamaño de P, pero como el tamaño de cada palabra basica es 5 letras o menos, ese factor es despreciable, dando un tiempo que es efectivamente lineal.

El otro caso es llenar la tabla para simbolos que dependen de otros simbolos. Digamos que la ecuacion para este simbolo es A = B + C. Eso tambien se puede resolver en tiempo O(P) con combinar los datos en la tabla para los simbolos B y C. Dejare ese aspecto de la solucion como una asignacion para el lector.

La respuesta final es YES si y solo si F[START][0] = |P|.