[T2] [P1] Tiempo de ejecucción

[ignaciomansuy]

Hola! En mi computador logré obtener un tiempo de ejecucción cercano a 1.2 segundos. Quería saber si existe un grado de flexibilidad respecto al timeout cuando corran los tests con M cercano a $10^5$? Porque asumo el tiempo variará según la máquina que utilicen para correrlos.

Saludos y gracias de antemano.

[mc-cari]

Hola. Si, el tiempo varía un poco según la máquina y es flexible. Por eso se da la complejidad esperada, si cumples con la complejidad el código cumplirá con el tiempo esperado.

[0wulf]

@mc-cari Mi código corre en un intervalo de 2 a 3 segundos para los inputs de orden máximo, debido a factores constantes, sin embargo posee la complejidad pedida. Esto se considerará correcto? Sé que es más del doble en algunos casos

[mc-cari]

Hola @0wulf, ya existe flexibilidad en el tiempo límite de 1 segundo así que es probable que la complejidad de tu código no sea la correcta. Además tienes que asegurarte que en ninguna variable se guarde un valor mayor a $10^9 + 9$ para que no afecte la complejidad.

[0wulf]

@mc-cari Estuve revisando mi código y de todas formas sí presenta la complejidad pedida. Se demora maximo 1.5s en calcular la respuesta luego de un pre-process con ordenamiento. Esos 1.5s se deben a que realizo m veces dos operaciones O(log(m)). Evidentemente si realizara una sola operación el tiempo de calcular la solucion ronda los 0.75s pero evidentemente mi approach requiere de ambas operaciones. ¿qué se puede hacer en tal caso?

[mc-cari]

@0wulf en el caso que la complejidad sea correcta no debiera haber problema con el tiempo cuando lo evalúe, voy a asegurar de que los códigos con complejidad correcta puedan pasar en tiempo.