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.
User avatar
ymondelo20
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

3540 - Exactly K Times

Postby ymondelo20 » Thu Mar 03, 2016 11:35 pm



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

HaZard
Posts: 113
Joined: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 3540 - Exactly K Times

Postby HaZard » Wed Oct 12, 2016 6:02 pm

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: 49
Joined: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 3540 - Exactly K Times

Postby frankr » Thu Oct 13, 2016 11:52 am

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
COJ Administrator
Posts: 1968
Joined: Sun Nov 13, 2011 12:32 pm
Location: Universidad de las Ciencias Informáticas
Gender: None specified
Contact:

Re: 3540 - Exactly K Times

Postby ymondelo20 » Thu Oct 13, 2016 9:16 pm

:( ... 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: 49
Joined: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 3540 - Exactly K Times

Postby frankr » Thu Oct 13, 2016 10:57 pm

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: Mon Oct 06, 2014 6:25 am
Gender: None specified

Re: 3540 - Exactly K Times

Postby humbertodiaz » Fri Oct 14, 2016 3:30 am

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: Mon Oct 26, 2015 6:20 pm
Gender: None specified

Re: 3540 - Exactly K Times

Postby isaac » Sun Oct 16, 2016 11:51 pm

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: Sun Feb 09, 2014 9:43 am
Location: Camagüey - Cuba
Gender: Male
Contact:

Re: 3540 - Exactly K Times

Postby HaZard » Thu Oct 20, 2016 3:02 pm

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: 49
Joined: Fri Nov 18, 2011 8:09 pm
Location: Las Tunas
Gender: Male

Re: 3540 - Exactly K Times

Postby frankr » Fri Oct 21, 2016 12:59 pm

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.


Return to “Problem set”

Who is online

Users browsing this forum: No registered users and 1 guest