¿Cómo puedo mejorar este algoritmo para evitar que TLE se envíe SPOJ?

Question

estoy tratando de resolver el siguiente problema: http://www.spoj.pl/problems/TRIP/

me escribió una solución utilizando DP (Dynamic Programming) en C++ (código publica a continuación). Pero obtengo TLE (límite de tiempo excedido). ¿Cómo puedo optimizar mi código?

#include<iostream> 
#include<cstdio> 
#include<string> 
#include<cstring> 
#include<vector> 
#include<algorithm> 
#include<cmath> 

using namespace std; 
string a,b; 
vector<string> v; 
int dp[85][85]; 

void filldp() 
{ 
    for(int i = 0; i <= a.length(); i++) 
     dp[i][0] = 0; 
    for(int i = 0; i <= b.length(); i++) 
     dp[0][i] = 0; 

    for(int i = 1; i <= a.length(); i++) 
     for(int j = 1; j<= b.length(); j++) 
     if(a[i-1] == b[j-1]) 
      dp[i][j] = dp[i-1][j-1] + 1; 
     else 
      dp[i][j] = max(dp[i-1][j], dp[i][j-1]); 
} 

vector<string> fillv(int i, int j) 
{ 
    vector<string> returnset; 
    if(i == 0 || j == 0) 
    { returnset.push_back(""); 
     return returnset; 
    } 

    if(a[i-1] == b[j-1]) 
     { 
      vector<string> set1 = fillv(i-1,j-1); 
      for(int k = 0; k < set1.size(); k++) 
      { 
      returnset.push_back(set1[k] + a[i-1]); 
     } 
      return returnset; 
     } 

    else 
     { 
      if(dp[i][j-1] >= dp[i-1][j]) 
      { 
       vector<string> set1 = fillv(i,j-1); 
       returnset.insert(returnset.end(), set1.begin(), set1.end()); 
      } 

      if(dp[i-1][j] >= dp[i][j-1]) 
      { 
       vector<string> set2 = fillv(i-1,j); 
       returnset.insert(returnset.end(), set2.begin(), set2.end()); 
      } 

      return returnset; 

     }  

} 

void output() 
{ 
    sort(v.begin(), v.end()); 
    v.erase(unique(v.begin(), v.end()), v.end()); 
    for(int i = 0; i < v.size(); i++) 
     cout << v[i] << endl; 
    cout << endl;  
} 

int main() 
{ 
    int T; 
    cin >> T; 

    while(T--) 
    { 
     memset(dp,-1,sizeof(dp)); 
     v.clear(); 
     cin >> a >> b; 
     filldp(); 
     v = fillv(a.length(), b.length()); 
     output(); 
    } 
    return 0; 
} 

Mi suposición aquí es que hay un montón de pasar alrededor de las estructuras de datos que se pueden evitar, pero no puedo averiguar cómo exactamente.

Answer 1

La primera cosa incorrecta que estás haciendo es usar cin y cout, que son terriblemente lentos. ¡Nunca use cin y cout para la programación del concurso! Pasé de TLE a AC simplemente cambiando cin/cout a scanf/printf.

Answer 2

Cuando conozca el tamaño máximo de la cantidad de respuestas, es mejor utilizar una matriz en lugar del vector porque es mucho más rápido que el vector. ("Hay al menos uno de estos viajes, pero nunca más de 1000 diferentes")

función fillv desperdicia mucho tiempo en el código. porque es obtener mucho espacio en tiempo de ejecución y liberarlo (debido al espacio local para la función fillv). es mejor usar una respuesta global para eso.

para la entrada y salida para completar la respuesta de "Gandalf the Grey", si desea utilizar cin y cout, es mejor usar std::ios::sync_with_stdio(false); (para acelerar su tiempo de ejecución) sin embargo printf y scanf es mucho más rápido que esto .

Answer 3

Puede reducir en gran medida el tiempo de ejecución tomando entradas usando fread() o fread_unlocked() (si su programa es de subproceso único). Bloquear/Desbloquear el flujo de entrada solo una vez lleva un tiempo insignificante, entonces ignórelo.

Aquí está el código:

#include <iostream> 

int maxio=1000000; 
char buf[maxio], *s = buf + maxio; 

inline char getc1(void) 
{ 
    if(s >= buf + maxio) { fread_unlocked(buf,sizeof(char),maxio,stdin); s = buf; } 
    return *(s++); 
} 
inline int input() 
{ 
    char t = getc1(); 
    int n=1,res=0; 
    while(t!='-' && !isdigit(t)) t=getc1(); if(t=='-') 
    { 
     n=-1; t=getc1(); 
    } 
    while(isdigit(t)) 
    { 
    res = 10*res + (t&15); 
    t=getc1(); 
    } 
    return res*n; 
} 

Esto se implementa en C++. En C, no necesitará incluir iostream, la función isdigit() está implícitamente disponible.

Puede tomar la entrada como una secuencia de caracteres llamando al getc1() y tomar la entrada entera llamando al input().

Toda la idea detrás de usar fread() es tomar grandes bloques de entrada a la vez. Llamar al scanf()/printf(), toma repetidamente un tiempo valioso en el bloqueo y desbloqueo de transmisiones, que es completamente redundante en un programa de subproceso único.

También asegúrese de que el valor de maxio es tal que todas las entradas se pueden tomar en unos pocos "viajes de ida y vuelta" solamente (idealmente uno, en este caso). Ajústalo según sea necesario. Esta técnica es altamente efectiva en la programación de competiciones, para obtener una ventaja sobre tu oponente en términos de tiempo de ejecución.

Espero que esto ayude!