3540 - Exactly K Times

[ymondelo20]

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

[HaZard]

Este es un problema bastante interesante, la mayoría de los usuarios lo resolvieron usando hash, otros no se como pasaron los juegos de datos, pero lo hicieron casi a fuerza bruta (vale igual si dio AC), otros con suffix array, creo que esta es la mas eficiente, pero tiene una solución de lo más interesante con KMP, piénsenla, Saludos

[frankr]

teruel, gracias por la sugerencia del KMP, pero solo se me ocurre un O(N^3), no es eso no?. Yo lo hice con hash en O(N^2 Log N), pero también me asombré de ver las FB O(N^3 Log N) aceptadas.

[ymondelo20]

... siempre son bienvenidos a proponer un nuevo dataset que de al traste con esas soluciones que no deberían ser aceptadas, respetando que el dataset esté dentro de los límites originales del problema.

En mi caso lo resolví utilizando un árbol de prefijos.

[frankr]

También podemos añadir la versión II del problema con rangos mayores. Particularmente me gusta la idea de que existan varias variantes de un problema con distintos grados de dificultad, eso contribuye al entrenamiento en general y en particular al de los estudiantes de preuniversitario porque sería el equivalente a las subtareas de las competencias como la IOI.

[humbertodiaz]

Cierto es. El uso de subtareas o multiples versiones de un problema es una excelente herramienta para permitirle a los estudiantes con menos experiencia a intentar algoritmos mas lentos, y para demostrar la importancia de la eficiencia de una manera muy concreta. La realidad es que a veces quisiera que se utilizaran subtareas en la ACM ICPC. Asi los novatos no se desmotivarian con su inabilidad de resolver un problema completo. Sin embargo, eso tambien requiere mas esfuerzo de parte de los autores, quienes ya estan muy ocupados a veces.

[isaac]

No se que tan facil o diicil sea hacer que el COJ califique subtareas, pero si seria interesante que cada problemsetter subiera varias versiones de sus problemas solamente aumentandoles el rango u otro detalle.

[HaZard]

teruel, gracias por la sugerencia del KMP, pero solo se me ocurre un O(N^3), no es eso no?. Yo lo hice con hash en O(N^2 Log N), pero también me asombré de ver las FB O(N^3 Log N) aceptadas.

Entiendo que hay una solución con KMP en O(N^3), pero es muy ineficiente, aunque con esos juegos de datos puede que pase, sin embargo puede hacerse una observación que lo reduce también a O(N^2 log N).

UPDATE: si existe una cadena de longitud L que aparece exactamente K veces, entonces se puede afirmar que existe una cadena de tamaño L - 1 que también aparece K veces, de ahí que se puede fijar el tamaño como en la solución N^3, pero con una búsqueda binaria, y solo chequear que exista la cadena con el KMP, lo que reduce la complejidad a O(N^2 log N) que es suficiente para pasar esos límites.

PD: con esa solución no se corre el riesgo que da el hash_table de colisiones con los módulos, aunque eso rara vez pasa, Saludos.

[frankr]

Claro, con búsqueda binaria, muy buena idea! A pesar de que ya lo hice por la vía del hashing voy a implementar esta otra idea. Gracias nuevamente teruel.