3540 - Exactly K Times

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:

3540 - Exactly K Times

Post by ymondelo20 » 2 years ago



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

HaZard
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3540 - Exactly K Times

Post by HaZard » 2 years ago

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
teruel

User avatar
frankr
Posts: 50
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: 3540 - Exactly K Times

Post by frankr » 2 years ago

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.

User avatar
ymondelo20
Posts: 1968
Joined: 7 years ago
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3540 - Exactly K Times

Post by ymondelo20 » 2 years ago

:( ... 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.
"Every problem has a simple, fast and wrong solution" OJ's Main Law. ;)

User avatar
frankr
Posts: 50
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: 3540 - Exactly K Times

Post by frankr » 2 years ago

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

Re: 3540 - Exactly K Times

Post by humbertodiaz » 2 years ago

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.

User avatar
isaac
Posts: 83
Joined: 3 years ago
Gender: None specified

Re: 3540 - Exactly K Times

Post by isaac » 2 years ago

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
Posts: 113
Joined: 4 years ago
Location: Camagüey - Cuba
Gender: Male
Contact:
Cuba

Re: 3540 - Exactly K Times

Post by HaZard » 2 years ago

frankr wrote: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.
teruel

User avatar
frankr
Posts: 50
Joined: 7 years ago
Location: Las Tunas
Gender: Male

Re: 3540 - Exactly K Times

Post by frankr » 2 years ago

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.

Post Reply

Return to “Problem set”