Here is the problem link: Problem Link: Minimum Cost to Convert String II

Here, I treated each string in the original and changed vectors as unique graph nodes. This involved computing the hash value for every string and subsequently compressing these values. Then I used Floyd-Warshall algorithm to facilitate the establishment of connections between these compressed nodes.

Since, the combined number of unique strings in the original and changed vectors would not exceed 200. We can easily apply Floyd-Warshall.

Now, having precomputed hash values for both the source and target strings, I can easily find the hash value of any substring in constant time, as it is a crucial step during dynamic programming (DP) transitions. The time complexity in the DP phase is O (string. length^2). Overall, our time complexity can reach a maximum of N^2*logN, comfortably below the given time limit.

Why am I still getting TLE?

MY CODE:

map<int,int>comp;
vector<vector<ll>>dist;
const static int N= 1001;
int powers[N];
int invPowers[N];

int n;
const ll INF= 1e13;
vector<ll>dp;

const int mod= 1e9+9;
const int pr= 29;

int binExp(int a, int b, int mod){
int ans=1;
while(b>0){
    if(b&1ll)ans=(ans*1ll*a)%mod;
    a=(a*1ll*a)%mod;
    b>>=1ll;
}
return ans;
}
void precompute(){
    powers[0]=1;
    powers[1]=pr;
    for(int i=1;i<N; i++)powers[i]= (pr*1ll*powers[i-1])%mod;
    invPowers[0]=1;
    for(int i=1; i<N; i++)invPowers[i]= binExp(powers[i], mod-2,mod);
}
void rollingHash(string &s, vector<int>&hashS){
    int sz= s.size();
    for(int  i=0; i<sz; i++){
        int hash= (powers[i]*1ll*(s[i]-'a'+1))%mod;
        hashS.push_back(hash);
    }
    for(int i=1; i<sz; i++)hashS[i]= (hashS[i]+hashS[i-1])%mod;
}
ll findSubstringHash(int &i, int &j, vector<int>&hashArr){
    ll inv= invPowers[i];
    ll val= (hashArr[j]-(i==0?0:hashArr[i-1]));
    if(val<0)val+= mod;
    val=(val*inv)%mod;

    return val;
}

ll f(int i, string &s, string &t, vector<int>&hashS, vector<int>&hashT){
    if(i>=n)return 0;

    if(dp[i]!=-1)return dp[i];
    ll ans= INF;

    for(int j=i; j<n; j++){
        int hash1= findSubstringHash(i,j,hashS);
        int hash2= findSubstringHash(i,j,hashT);
        if(hash1==hash2)ans=min(ans, f(j+1,s,t,hashS,hashT));
        else if(comp.find(hash1)!=comp.end() && comp.find(hash2)!=comp.end()){
            int i1= comp[hash1], j1= comp[hash2];
            ans=min(ans, dist[i1][j1]+ f(j+1,s,t,hashS,hashT));
        }    
    }

    return dp[i]= ans;
}

long long minimumCost(string s, string t, vector<string>& org, vector<string>& ch, vector<int>& cost) {
    int sz= org.size();
    vector<int>hashS, hashT;
    precompute();
    rollingHash(s,hashS);
    rollingHash(t,hashT);
    vector<int>storeHashes1, storeHashes2;
    for(int i=0; i<sz; i++){
        vector<int>a,b;
        rollingHash(org[i],a);
        rollingHash(ch[i],b);
        storeHashes1.push_back(a.back());
        storeHashes2.push_back(b.back());
        comp[a.back()];
        comp[b.back()];
    }

    int ptr=0;
    for(auto &ele: comp)ele.second=ptr++;

    dist.resize(ptr,vector<ll>(ptr,INF));

    for(int i=0; i<ptr; i++)dist[i][i]=0;


    for(int i=0; i<sz; i++){

        int i1= comp[storeHashes1[i]];
        int j1= comp[storeHashes2[i]];

        if(dist[i1][j1]>cost[i])
        dist[i1][j1]= cost[i];
    }

   //10^6
    for(int k=0; k<ptr; k++){
        for(int i=0; i<ptr; i++){
            for(int j=0; j<ptr; j++){
                if((dist[i][k]!=INF && dist[k][j]!=INF) && dist[i][j]>dist[i][k]+dist[k][j]) dist[i][j]= dist[i][k]+dist[k][j];
            }
        }
    }

    n=s.size();

    dp.resize(n+1,-1);
    ll ans= f(0,s,t,hashS,hashT);

    if(ans>=INF)return -1;
    return ans;

}

Hi All, In the Spoj Problem ABCPATH- ABC Path, I am not able to figure out: why my code is getting runtime error?

Here is the link to problem: ABC PATHhttps://www.spoj.com/problems/ABCPATH/

Here is my code: ~~~~~

pragma GCC optimize("O3,unroll-loops")

pragma GCC optimize(3, "Ofast", "inline")

include<bits/stdc++.h>

using namespace std; using namespace chrono;

define endl "\n"

define _USE_MATH_DEFINES

include

ifndef M_PI

#define M_PI 3.14159265358979323846

endif

define int long long int

define pb push_back

define mk make_pair

define ppb pop_back

define pf push_front

define ppf pop_front

define all(x) (x).begin(),(x).end()

define ub upper_bound

define lb lower_bound

define uniq(v) (v).erase(unique(all(v)),(v).end())

define sz(x) (int)((x).size())

define fr first

define sc second

define pii pair<int,int>

define rep(i,a,b) for(int i=a;i<b;i++)

define mem1(a) memset(a,-1,sizeof(a))

define mem0(a) memset(a,0,sizeof(a))

define ppc __builtin_popcount

define ppcll __builtin_popcountll

int const N=2*1e5+10; //int const INF=1e18; int mod=1e9+7; int mod1=998244353; const int INF=1e4;

define fastio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)

int r,c; int dx[]={1,1,-1,-1,0,0,1,-1}; int dy[]={1,-1,1,-1,1,-1,0,0}; bool vis[60][60]; vector<vector>grid; int mx=0;

bool is_valid(int i, int j){ return (i>=0 && j>=0 && i<r && j<c); }

void dfs(int i, int j, int l){ if(vis[i][j])return;

vis[i][j]=1; mx=max(mx,l);

rep(k,0,8){ int x=i+dx[k]; int y=j+dy[k]; if(vis[x][y] || !is_valid(x,y))continue;

if(grid[x][y]-grid[i][j]==1)
  dfs(x,y,l+1);

} }

void solve(){ int k=0; while(cin>>r>>c){ if(!r && !c)break;

grid.resize(r,vector<char>(c));
// vis.resize(r,vector<bool>(c,false));
// cout<<grid.size()<<" "<<grid[0].size()<<endl;
rep(i,0,r){
  string s; cin>>s;
  rep(j,0,c){
    grid[i][j]=s[j];
   // cout<<vis[i][j]<<" ";
  }
 // cout<<endl;
}
memset(vis,false,sizeof(vis));

// mx=0;

rep(i,0,r){
  rep(j,0,c){
    if(grid[i][j]=='A')dfs(i,j,1);
  }
}

cout<<"Case "<<++k<<": "<<mx<<endl;
mx=0;

} return; }

signed main(){ #ifndef ONLINE_JUDGE freopen("INPUT1.txt","r",stdin); freopen("out1.txt","w",stdout); #endif

fastio();
auto start1 = high_resolution_clock::now();
int t=1;
//cin>>t;

// precompute();

//fill_dp();
while(t--){
  solve();
}
auto stop1 = high_resolution_clock::now();
auto duration = duration_cast<microseconds>(stop1 - start1);
#ifndef ONLINE_JUDGE
cout << "Time: " << duration . count() / 1000 <<"ms"<<endl;
#endif

return 0; }

~~~~~

`