Duda con un error

Jueces Online OIAJ
#1

En algunos casos de un problema me tira Execution timed out (wall clock limit exceeded), ¿qué significa?

#2

¡Hola!

Es un error de tiempo límite excedido, pero no por “cantidad de uso de CPU”, que es lo normal, sino “por tiempo total”. O sea: el programa tarda mucho tiempo, pero ese tiempo no lo está usando “ejecutando normalmente”.

Generalmente es consecuencia de alguna de las siguientes:

  • Utilizar mucha memoria: aunque no se pase del límite máximo de 512MB, usar mucha memoria toma mucho más tiempo que los cálculos normales y podría generar un tiempo límite excedido.
  • Algún error en el programa, que genera comportamiento extraño (como por ejemplo acceder fuera del rango de un arreglo, o guardar referencias a variables obsoletas).

En tu caso, casi seguro que es lo primero. En esta línea

     vector <vector <int> > v(n*m + 1);

Se crean muchíiiiiiiiiisimos vector chiquititos: no solo un vector por fila, que sería inofensivo, sino uno por casilla, y después se hacen muchísimos pushback a estos vectorcitos. Esto es bastante ineficiente en este caso, y muy especialmente en la parte de reserva de memoria, porque en general todas estas estructuras tienen un cierto costo “fijo” de pedir memoria bastante apreciable, que cuando tenemos “un solo vector grande” no afecta en nada, pero si tenemos “quichicientos vectors chiquititos” se vuelve un costo apreciable en uso de memoria y tiempo de reserva de memoria.

Yo creo que en este caso se puede evitar la situación no guardando todo el grafo explícitamente de esta manera, sino trabajando directamente con el grafo implícito: cuando tenemos un cierto (x,y), sabemos quiénes son sus vecinos, así que siempre que queramos usar sus vecinos, podemos generarlos en ese momento, sin tener que guardarse absolutamente todo el grafo en memoria explícitamente con todo el detalle. Esto es lo ideal en casi todos los problemas que trabajen con “grillas” o “tableros”, como este.

Un truquito clásico para evitarse los 4 ifs de las direcciones, es tener arreglos con los desplazamientos.

    const int dx[4] = {0,1,0,-1};
    const int dy[4] = {1,0,-1,0};
    // ...
    for (int dir = 0; dir < 4; dir++)
    {
        int nx = x + dx[dir];
        int ny = y + dy[dir];
        // (nx,ny) es uno de los vecinos de (x,y)
    }
3 Me gusta
#3

El “truquito clásico” mencionado ya está en la wiki oficial de oia! http://wiki.oia.unsam.edu.ar/algoritmos-oia/grafos/bfs/distintas-movidas-en-tablero

Y se puede leer más sobre bfs acá: http://wiki.oia.unsam.edu.ar/algoritmos-oia/grafos/bfs

3 Me gusta
#4

Y también está el concepto de grafo implícito, que mencioné en la respuesta

http://wiki.oia.unsam.edu.ar/algoritmos-oia/grafos#representacion_en_la_computadora

1 me gusta