How can I improve this algorithm to prevent TLE is SPOJ submission?

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 posted 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 guess here is that there is a lot of passing around of data structures which can be avoided but I cannot exactly figure out how.

Answer 1

The first wrong thing you're doing is using cin and cout, which are terribly slow. Never use cin and cout for contest programming! I've gone from TLE to AC just by changing cin/cout to scanf/printf.

Answer 2

You can greatly reduce the time of execution by taking input using fread() or fread_unlocked() (if your program is single-threaded). Locking/Unlocking the input stream just once takes negligible time, so ignore that.

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 won't need to include iostream, function isdigit() is implicitly available.

You can take input as a stream of chars by calling getc1() and take integer input by calling input().

The whole idea behind using fread() is to take large blocks of input at once. Calling scanf()/printf(), repeatedly takes up valuable time in locking and unlocking streams which is completely redundant in a single-threaded program.

Also make sure that the value of maxio is such that all input can be taken in a few "roundtrips" only (ideally one, in this case). Tweak it as necessary. This technique is highly effective in programming competitions, for gaining an edge over your opponent in terms of time of execution.

Hope this helps!