1740 - Another Palindrome Problem II

[ymondelo20]

http://coj.uci.cu/24h/problem.xhtml?abb=1740

[frankr]

Este problema parece q solo está etiqueteado con el tag de Strings. Pienso que debería incluirse en DP también porque hay una solución con esta técnica.

[ymondelo20]

En realidad todo la solución está basada más bien en DS (no strings)... el DP que lleva es a un nivel menos complicado.

[frankr]

Qué quiere decir DS? Data Structure? Yo sigo insistiendo que hay una solución O(n^2) que consiste de dos DPs: una para los palindromos y otra para contar.

[ymondelo20]

DS es Data Structure.
La solución si es |S| ^ 2.
Al parecer no revisaste de nuevo, las etiquetas ya habían sido actualizadas.

Saludos.
Y.

[frankr]

Ya se actualizaron los tags, gracias! Es q siempre me gusta pensar las solciones a los problemas por la vía más elemental posible, con el mínimo de recursos necesarios. Con esto no quiero negar los algortimos y DS avanzados, solo lo hago para ponerme en el lugar de un concursante de IPVCE, que no conozca Estructuras avanzadas, ni algoritmos o ideas que se adquieren en la universidad, y pienso como podría resolver un problema DIFÍCIL con las herramientas a su alcance.

[ymondelo20]

Comprensible...
No veo forma de resolverlo sin hacer uso de estructuras de datos para hallar todos los intervalos que son palíndromes.
Sin embargo es cierto que la solución tiene siempre asociada la programación dinámica, para facilitar el conteo de las soluciones finales.

[frankr]

A qué estructura de datos te refieres en este caso? Una simple matriz booleana + un algoritmo n^2 o algo más complejo.

[ymondelo20]

En mi caso, la estructura de datos resultante de aplicar Manacher.

[frankr]

Yo considero ese algoritmo demasiado complicado para introducirlo a estudiantes del ipvce. Y gracias a que los rangos lo permiten ideamos una solución con DP, clara y sencilla de explicar, sin usar este algoritmo y para sorpresa nuestra es una de las mejores soluciones. Claro q si aumentan los rangos del problema la nuestra no da en tiempo.