How can I improve this algorithm to prevent TLE?

Question

I am trying to solve the following problem: http://www.spoj.pl/problems/TRIP/

I wrote a solution using DP (dynamic programming) in C ++ (code below). But I get TLE (time limit exceeded). How can I optimize my code?

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

My assumption is that there is a lot to go around around data structures, which can be avoided, but I cannot figure out exactly how to do this.

Answer 1

The first wrong thing you do is use cin and cout, which are terribly slow. Never use cin and cout for competitive programming! I switched from TLE to AC, just changing cin / cout to scanf / printf.

Answer 2

You can significantly reduce the execution time by entering with fread() or fread_unlocked() (if your program is single-threaded). Locking / unlocking the input stream takes only a short time once, so ignore it.

Here is the code:

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

This is implemented in C++ . In C you do not need to enable iostream , the isdigit() function is implicitly available.

You can accept input as a stream of characters by calling getc1() and accept integer input by calling input() .

The whole idea of ​​using fread() is to immediately accept large input blocks. Calling scanf()/printf() repeatedly takes up valuable time when locking and unlocking threads that are fully reserved in a single-threaded program.

Also, make sure that the maxio value is such that all input can only be done in a few “circular transitions” (ideally, in this case). Adjust it if necessary. This method is very effective in programming competitions to gain an edge over your opponent in terms of lead time.

Hope this helps!

Answer 3

when you know the maximum size of the number of answers, it is better to use an array instead of a vector because it is much faster than the vector. ("There is at least one such journey, but no more than 1000 different")

Function

fillv is time consuming in code. because it gets a lot of space at runtime and frees it up (due to the local space for the fillv function). for this it is better to use a global response.

for input and output to complete the answer "Gandalf the Gray", if you want to use cin and cout, it is better to use std::ios::sync_with_stdio(false); (to speed up the io runtime), however printf and scanf are much faster than that.