Juez en línea de Esfera (SPOJ): ¿Por qué el siguiente código da como resultado TLE? Quiero saber cómo se puede optimizar mi código para evitarlo.

TLE como su nombre indica claramente es Tiempo límite excedido, es decir, la ejecución de su programa no había terminado en el límite de tiempo especificado.
Podría haber muchas razones para eso.

1. Problema con el algoritmo: Tal vez estás tratando de resolver un problema de O (n) en O (n ^ 2) o algo así. En un segundo, en ideone, puede realizar alrededor de 10 ^ 7 cálculos.

2. Lenguaje más lento: los creadores de problemas generalmente establecen un límite de tiempo de acuerdo con lenguajes rápidos como C, C ++ y lenguajes más lentos como python y java pueden tener dificultades para resolver el problema en un límite de tiempo específico.

3. Salida de entrada lenta : su método de lectura de entrada y escritura de salida es demasiado lento. En Java, no use un escáner; use un BufferedReader en su lugar. En C ++, no use cin / cout; use scanf e printf en su lugar.

Gracias por A2A.

Como otros ya han mencionado, TLE es tiempo límite excedido.
TLE se debe principalmente a 2 razones.

1. Algoritmo Lento
2. Método lento de entrada / salida.

1. Algoritmo lento
Para evitar el problema de Algoritmo lento, debe practicar regularmente y a medida que se acostumbre a más y más técnicas / trucos, este problema se eliminará gradualmente. Para superar este problema, siéntase cómodo con el uso de estructuras de datos de manera efectiva, lo que solo viene con la práctica.
Por ejemplo: necesita encontrar la suma de los elementos de la matriz del índice i a j. Usando el enfoque clásico, esto llevaría O (n) tiempo. Sin embargo, si utiliza un “árbol de segmentos”, que es una estructura de datos simple pero meticulosamente implementada, puede realizar la tarea en tiempo O (log n). ¡¡Imagina eso!! (Como nota al margen: la construcción del árbol lleva tiempo O (n * log n). Del mismo modo, si utiliza trucos de memorización (programación dinámica) en lugar de calcular los subproblemas una y otra vez, se ahorra mucho tiempo.

A veces, necesitas innovar en el lugar (y reunir trucos mientras practicas).
Por ejemplo: si necesita verificar si un número es primo, el enfoque trivial sería ejecutar un ciclo de 1 a ese número y verificar el número de factores. Sin embargo, si piensa detenidamente, se dará cuenta de que la tarea simplemente se puede lograr ejecutando el ciclo hasta sqrt (número). (¡Piénsalo!).

Se trataba de utilizar mejores algoritmos y estructuras de datos. Sin embargo, a veces, aunque pueda estar utilizando un algoritmo efectivo, aún puede obtener un TLE. Esto nos lleva a la segunda parte de la respuesta.

2. Método de entrada / salida lenta:
En C ++, el uso de scanf e printf en lugar de cin / cout puede ahorrar mucho tiempo.
Sin embargo, en ciertos problemas, pero raros, los datos de entrada / salida pueden ser muy grandes, por lo que a veces scanf e printf también pueden no ser suficientes. Para mejorar ese aspecto, debe llegar a la construcción central del lenguaje de programación que utiliza.
Por ejemplo: supongamos que el archivo de entrada consta de una gran cantidad de líneas, cada una de las cuales contiene un número entero. En lugar de “escanear” los enteros, un mejor enfoque es leer la línea suponiendo que es una cadena y luego usar ciertas funciones predefinidas que convierten la cadena al entero. (por ejemplo, un número que dice 46 se lee como una cadena usando la función “fread” , sin embargo, se puede convertir a int usando una función “atio ()” . Esto es considerablemente más rápido.

Estas funciones son específicas de C ++, sin embargo, mi objetivo es ilustrar mi punto. Por lo tanto, investigue sobre métodos de entrada / salida más rápidos específicos para el idioma que utiliza.

Nota importante: Obtener un TLE no significa que su respuesta sea correcta. Entonces, si está obteniendo un TLE, primero trabaje en optimizar su enfoque y luego si está obteniendo una respuesta incorrecta (lo cual es común si es un principiante) intente encontrar los errores.

TLE (límite de tiempo excedido) puede atascarte de las siguientes maneras:
1. Bucle infinito.
2. La complejidad de su código es mayor que la complejidad requerida para obtener AC.
3. Su método de lectura de entrada y salida de escritura es demasiado lento.
4. El lenguaje puede ser un problema, ya que Python es un poco más lento que C ++ debido a su naturaleza encapsulante. En Python, puede intentar acelerar sus soluciones agregando las siguientes dos líneas al inicio de su archivo:

  importar psico
 psyco.full () 

Más puede encontrar en ¿Por qué obtengo un límite de tiempo excedido?

El culpable es probablemente la línea 29.

for (int k = 0; k < 4; k++) { 

Como estás usando un dfs iterado, vas a tratar con el mismo vértice 4 veces (5 para el vértice inicial) en el peor de los casos. Esto da un total de 13 ejecuciones del bucle, mientras que solo 4 son necesarias. El problema se vuelve más grave en los gráficos en los que podría tener vértices con grandes grados.

Para deshacerse de esto, intente uno de los siguientes:

• Use una matriz para k que sepa cuántos vecinos de cada vértice ya se han procesado para que no tengan que ser tratados la próxima vez.
• Use dfs recursivo que hace esto automáticamente. Sin embargo, esto podría tener otros gastos generales
• Use bfs en lugar de dfs para encontrar el punto más alejado. Esta es probablemente la mejor opción, ya que manejas un vértice solo una vez. Tengo una solución aceptada usando esto

Si ninguno de estos funciona, debe intentar resolver el problema utilizando un dfs en lugar de dos. Hay un árbol simple dp que da la solución sin el requisito de dos recorridos.

Muchos de los puntos que causan TLE ya se han mencionado en las respuestas a continuación. Pero, hay algunos puntos que comprenderá usted mismo después de una buena cantidad de práctica. Déjame ahorrarte algo de tiempo en la depuración:

1) Diferencia entre cout / cin :: printf / scanf: se sabe que printf / scanf es relativamente muy rápido que cout / cin. Use estas alternativas siempre que sea posible.

2) Utilice “continuar”, “descanso” cuando sea necesario. Ahorra algo de tiempo.

3) Al escribir funciones, si está configurando un valor de retorno en algún lugar y no está realizando ninguna otra restauración de variables hasta la declaración de retorno, devuelva el valor de retorno en la posición anterior. Ahorra algo de tiempo.

4) Intente usar contenedores con una cantidad relativamente menor de tiempo total que todas sus operaciones toman. Elige tu contenedor sabiamente.

Límite de tiempo excedido.
Significa que el tiempo de ejecución de su algoritmo es demasiado alto y excede el tiempo máximo permitido en el problema.