3102 - Word Equations

Discussion around the problems of the COJ.
Forum rules
Remember that posting AC code is not allowed here. If you are going to ask a question or to post a solution, describe your algorithm instead. Posting AC code will be penalized.
Post Reply
User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3102 - Word Equations

Post by ymondelo20 » 4 years ago



"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
jose92
Posts: 24
Joined: 5 years ago
Location: Cienfuegos
Gender: None specified

Re: 3102 - Word Equations

Post by jose92 » 4 years ago

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
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 3102 - Word Equations

Post by humbertodiaz » 4 years ago

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.

User avatar
Dariel
Posts: 51
Joined: 7 years ago
Location: Santiago de Cuba
Gender: None specified
Contact:

Re: 3102 - Word Equations

Post by Dariel » 4 years ago

Puedes explicar la idea de como resolver este ejercicio??

humbertodiaz
Posts: 97
Joined: 5 years ago
Gender: None specified

Re: 3102 - Word Equations

Post by humbertodiaz » 4 years ago

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|.

Post Reply

Return to “Problem set”