3

El objetivo de este programa es comprobar si hay algún número que divida a todos los demás. La variable t indica el número de casos totales, y la variable n el número de elementos en el vector. Este programa es para un juez online y me da un error de timeout por lo que tendría que optimizarlo, ¿cómo podría hacerlo?

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int t;
    cin>>t;
    for (int o = 1; o<=t; o++){
        int n;
        cin>>n;
        vector<long long int> arr;
        int cont = 0;
        bool esDivisible = false;
        for (int i = 0; i<n; i++){
            long long int a;
            cin>>a;
            arr.push_back(a);
        }
        for(int i=0;i<n;i++){
            cont = 0;
            for(int j=0;j<n;j++){
                if(arr[j]%arr[i]==0){
                    cont++;
                }
                if(cont == n){
                    esDivisible = true;
                    break;
                }
            }
            if(esDivisible){
                break;
            }
        }


        if(esDivisible){
            cout << "SI\n";
        }
        else{
            cout << "NO\n";
        }
    }
}
        
1
  • 1
    Ahorita miro el problema, solo como una nota: Si la variable representa el numeros de casos, porque llamarla t? Porque no se llama numero_casos? Hay que darle buenos nombres a las cosas para que los demas te entiendan facil. el 6 ene. 2021 a las 20:01

2 respuestas 2

4

Este tipo de programas tienen trampa y es que se ciñen a unos requisitos en cuanto a tiempo de ejecución muy ajustados. Las soluciones generales no suelen dar buenos resultados.

Sincronización I/O

Lo primero que debes hacer es optimizar la entrada/salida. Por defecto, en C++ la I/O propia de C++ está sincronizada con la heredada de C. Esto impone una latencia que penaliza en exceso los tiempos de ejecución del programa.

Para desincronizar la entrada/salida basta con ejecutar:

std::ios_base::sync_with_stdio(false);

Puedes encontrar un ejemplo aquí

Como puedes ver, desactivar el sincronismo mejora los tiempos de lectura (en el caso del ejemplo la lectura es unas 4 veces más rápida)

Eso sí, al desactivar la sincronziación deja de ser seguro mezclar lecturas de stdio y de cin, así como las escrituras de stdout y cout.

Memoria dinámica

Por otro lado, debes intentar es reducir las reservas de memoria dinámica al máximo. Hacer una reserva de memoria dinámica es un proceso lento y laborioso que se come unos preciados ciclos de reloj... si se acaban haciendo reservas innecesarias, el tiempo se escapará entre tus dedos.

En tu caso es probable que el vector arr se esté redimensionando innecesariamente varias veces. Piensa que el árbitro puede llegar a meter 10k elementos o más en el array (el número máximo suele venir indicado).

Eliminar las reservas innecesarias de memoria es tán sencillo como llamar a reserve:

vector<long long int> arr;
arr.reserve(10000); // Maximo de elementos

Claro que, si te fijas, en tu caso estás creando un array para cada test. Eso implica que, para cada test, hay que crear un array (con la correspondiente reserva de memoria inicial) y destruir dicho array. Nuevamente es un trabajo totalmente innecesario.

Es preferible crear el array una sola vez y reutilizarlo en cada caso de prueba

vector<long long int> arr;
arr.reserve(10000); // Maximo de elementos

for (int o = 1; o<=t; o++){

    // ...

    arr.clear();
}

Vale, nuevo problema, hay que llamar a clear al final de cada caso para vaciar el array ... nuevamente es un trabajo que podemos eliminar con algunos cambios:

vector<long long int> arr;
arr.resize(10000);

for (int o = 1; o<=t; o++){
    int n;
    cin>>n;
    int cont = 0;
    bool esDivisible = false;
    for (int i = 0; i<n; i++){
        cin>>arr[i];
    }
    for(int i=0;i<n;i++){
        cont = 0;
        for(int j=0;j<n;j++){
            if(arr[j]%arr[i]==0){
                cont++;
            }
            if(cont == n){
                esDivisible = true;
                break;
            }
        }
        if(esDivisible){
            break;
        }
    }

Ahora no llamamos a reserve sino a resize. Esto hace que el vector automáticamente se llene de 10000 elementos con valor inicial 0. En cada caso de prueba utilizaremos únicamente n elementos, el resto nos da igual que existan o no ya que no vamos a acceder a ellos.

Vaya, resulta que ahora estamos inicializando todos los elementos del array a 0 para, posteriormente, dar a algunos de esos elementos un valor válido. Quizás debiéramos evitar esa inicialización a 0 para arañar algo al reloj. Lamentablemente std::vector no te permite crear los elementos sin inicializarlos. Tenemos que pasar a usar punteros y arrays:

long long int * arr = new long long int[10000];

// ...

delete[] arr;

¿Y ahora?

Llegados a este punto hemos eliminado los cuellos de botella más evidentes, no obstante el programa podría ser todavía más óptimo aplicando algunos cambios.

Así, por ejemplo, se podrían evitar las iteraciones innecesarias.

Sabemos que un número x no va a ser un divisor del conjunto arr si el resto de alguna división es distinto de 0. Si se da esa circunstancia no tiene sentido seguir comprobando el resto de números ya que tenemos la certeza que x no es solución:

int j;
for(j=0;j<n;j++){
    if(arr[j]%arr[i]!=0) break;
}

if( j == n )
{
  esDivisible = true;
  break;
}

El programa podría seguir mejorándose, eliminando acciones innecesarias, cacheando resultados intermedios para evitar repetir cálculos, ... corre de tu cuenta el seguir investigando otras optimizaciones.

2
  • if( sombrero.Puesto ) sombrero.quitar(); Me has hecho buscar la mitad de la respuesta en google para ver qué hacen algunas cosas, pero como dicen, el saber no ocupa lugar. Una pregunta sin embargo, si no te importa, en algunos ejemplos he visto usar long long y en otros long long int, y ambos parecen dar el mismo resultado. Sus rangos son iguales?
    – Benito-B
    el 6 ene. 2021 a las 21:23
  • 1
    @Benito-B es exactamente lo mismo. Te da igual poner long long o long long int, de la misma manera que long y long int son igualmente idénticos
    – eferion
    el 6 ene. 2021 a las 21:28
2

Bueno a primera vista veo que se puede optimizar lo siguiente:

 // Array auxiliar que usaremos para marcar con 1 uno la 
 // posición del elemento del array inicial que no ha sido
 // divisible al menos por un número del array.
 int arrAux[n];
   
 for(int i=0; i<n; i++) {
    // Compruebo si el elemento tuvo problemas de divisibilidad,
    // si es que sí (1) entonces vuelve al bucle. 
    if (arrAux[i] == 1) continue;
        
    esDivisible=true; // Por defecto pongamos que es divisible
        
    for(int j=0; j<n; j++) {
       // Si el número no es divisible no sigo comparando y salgo del bucle
       if(arr[j]%arr[i]!=0) {
           esDivisible=false;
           // Asigno un 1 para indicar que el elemento en esa posición no es
           // divisible al menos por un número del array.
           // Ahora se que (arr[j]%arr[i] != 0) y ahora me aseguro
           // que (arr[i]%arr[j] != 0) también es indivisible antes de 
           // marcarlo como tal en el array auxiliar.
           if (arr[i]%arr[j] != 0)
              arrAux[j] = 1;  
                          
           break;
       }
    }
    // Si en este punto no hubo que entrar en el
    // condicional del bucle anterior quiere decirse
    // que arr[i] fue divisible por todos y terminamos.
    if(esDivisible){
       break;
    }
 }
 // ---------------- Muestra resultado
 if(esDivisible){
     cout << "SI\n";
 }
 else{
     cout << "NO\n";
 }

Observa que nos ahorramos bastantes cálculos al no seguir comparando si es que ya no fue divisible por alguno. Y además al usar el array auxiliar también evitamos un montón de cálculos. Piensa que si el elemento en la posición 5000 no es divisible por el que está en la posición 5001 y viceversa salimos del bucle y no sigo comparando y cuando a continuación voy a comparar el elemento en la posición 5001 con el resto pues ya no lo hago porque a través del array auxiliar sé que existe al menos un número que no lo divide.

Espero se me haya entendido.

2
  • arrAux[n] es un VLA y no está soportado por el estándar de c++. Y aunque haya algún compilador que lo acepte, crear un VLA de 10k elementos puede consumir toda la pila del programa
    – eferion
    el 6 ene. 2021 a las 21:48
  • Lo que dices de ahorrar divisiones puede mejorar tiempos... o no. Piensa que acceder a los arrays puede provocar paginacion de la caché y ese es un proceso que consume bastante tiempo. Lo mejor en estos casos es tomar métricas para saber cuándo ese cambio es beneficioso y cuándo perjudicial
    – eferion
    el 6 ene. 2021 a las 21:51

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.