[T3] Complejidad del problema

[Coolgatty]

Hola, veo que piden una complejidad de n log n para cada instancia de test, pero como el problema consiste en ver si cada uno de los k-desplazamientos coincide al superponerse, entonces tenemos que resolver un problema que se resuelve en n log n, n veces. Esto termina siendo n^2 log n y no logro ver como se puede reducir esto ya que en si el problema lo requiere.

Vi que le respondieron en #18 pero esa respuesta no me deja conforme. Yo ya resolvi el problema de ver si una string desplazada coincide al superponerse, lo cual se resuelve en n log n, pero como piden resolverlo para cada uno de los k desplazamientos no creo que sea posible resolverlo en n log n el problema completo.

Porfavor si pueden dar mas aclaracion con respecto a este tema ya que de verdad no veo una forma de resolver el problema con tan solo UNA convolucion por test.

[N9199]

La cosa es que se puede hacer en $n\cdot\log n$, uno hace una multiplicación y después revisar todos los posibles periodos tambien es $n\cdot\log n$. Eso tiene que ver con un análisis más fino de la complejidad de esa verificación. No puedo aclarar mucho más ya que en ese punto estaría dando la solución, pero puedo intentarlo si es necesario.

[Coolgatty]

Una pregunta que ojala me puedas responder; debo buscar los periodos en despues de aplicat fft^-1 o puedo encontrar los periodos en el dominio frecuencia?