i had done this question through top down memorization. here is my code, I am getting TLE.
video link- blob:https://online.codingblocks.com/98d9663f-5f96-4112-a993-cd516f6a8cc6
#include<bits/stdc++.h>
using namespace std;
int fun(vector a,vector b, int n, int m, int k , vector<vector> &v)
{
if(n==0|| m==0)
return 0;
if(v[n][m]!=-1)
return v[n][m];
if(a[n-1]==b[m-1])
return 1+fun(a,b,n-1,m-1,k,v);
else
{
int p=0,q,r;
if(k>0)
p=1+fun(a,b,n-1,m-1,k-1,v);
q=fun(a,b,n,m-1,k,v);
r=fun(a,b,n-1,m,k,v);
v[n][m]=max(p,max(q,r));
return v[n][m];
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int i,j,n,m,k;
cin>>n>>m>>k;
vector a(n),b(m);
for(i=0;i<n;i++)
{
cin>>a[i];
}
for(i=0;i<m;i++)
{
cin>>b[i];
}
vector<vector> v(n+1,vector(m+1,-1));
cout<<fun(a,b,n,m,k,v);
}
K order LCS TLE
Sure
https://ide.geeksforgeeks.org/K2WOpAaVC8
it is giving tle on hackerearth question - Mancunian and K-Ordered LCS
link of the question- https://www.hackerearth.com/problem/algorithm/mancunian-and-k-ordered-lcs-e6a4b8c6/
Hey Rishab, as you are using top down approach its not working for larger inputs so i would suggest you to use 3D DP approach because its more efficient and will handle the larger inputs also.
why its not working, as my space is optimised more than 3d dp.
Because its time complexity is greater and TLE is time limit error. You can take more space but you should optimize the time.
Since I am doing memorization and there are 2 states in it, I think the complexity is O(n^2). Can you check it once again. how its complexity is more.
After doing 3d dp, its now showing memory limit exceeded error -
code - https://ide.geeksforgeeks.org/k3bP9IFSWG
Can someone check it on hackerearth https://www.hackerearth.com/problem/algorithm/mancunian-and-k-ordered-lcs-e6a4b8c6/