Come posso migliorare questo algoritmo per impedire che TLE sia inviato da SPOJ?

Question

Sto cercando di risolvere il seguente problema: http://www.spoj.pl/problems/TRIP/

ho scritto una soluzione che utilizza DP (Programmazione Dinamica) in C++ (codice pubblicato sotto). Ma ottengo TLE (limite di tempo superato). Come posso ottimizzare il mio codice?

#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; 
} 

La mia ipotesi è che c'è un sacco di passando intorno di strutture di dati che possono essere evitati, ma non riesco a capire come esattamente.

Answer 1

La prima cosa sbagliata che stai facendo è usare cin e cout, che sono terribilmente lenti. Non usare mai cin e cout per la programmazione di contest! Sono passato da TLE a AC semplicemente cambiando cin/cout a scanf/printf.

Answer 2

quando si conosce la dimensione massima del numero di risposte, è preferibile utilizzare la matrice anziché il vettore perché è molto più veloce del vettore. ("C'è almeno uno di questi viaggi, ma mai più di 1000 diversi")

la funzione fillv spreca molto tempo nel codice. perché occupa molto spazio in runtime e lo libera (a causa dello spazio locale per la funzione fillv). è meglio usare una risposta globale per questo.

per l'input e l'output per completare la risposta di "Gandalf the Gray", se ti piace usare cin e cout, è meglio usare std::ios::sync_with_stdio(false); (per accelerare il tuo runtime io) tuttavia printf e scanf è molto più veloce di questo .

Answer 3

È possibile ridurre notevolmente il tempo di esecuzione prendendo l'input utilizzando fread() o fread_unlocked() (se il programma è a thread singolo). Bloccare/sbloccare il flusso di input solo una volta richiede un tempo trascurabile, quindi ignoralo.

Ecco il codice:

#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; 
} 

Questo è implementato in C++. In C, non è necessario includere iostream, la funzione isdigit() è implicitamente disponibile.

È possibile prendere input come un flusso di caratteri chiamando getc1() e prendere l'intero numero chiamando input().

L'idea alla base dell'utilizzo di fread() consiste nel prendere grandi blocchi di input contemporaneamente. Chiamando il numero scanf()/printf(), si impiegano ripetutamente tempo prezioso per bloccare e sbloccare flussi che sono completamente ridondanti in un programma a thread singolo.

Verificare inoltre che il valore di maxio sia tale che tutti gli input possano essere presi solo in alcuni "roundtrip" (idealmente uno, in questo caso). Modificalo se necessario. Questa tecnica è molto efficace nella programmazione delle competizioni, per ottenere un vantaggio sul tuo avversario in termini di tempo di esecuzione.

Spero che questo aiuti!