Discount on crackers : getting tle. but working with sample test cases

CodeChef-DSA-learners
1

problem : Discount on crackers

#include <bits/stdc++.h>
using namespace std;
class Graph
{ public:
    map<char,list<char>> l;
void addedge( char a, char b)
{
    l[a].push_back(b);
}
map <char,bool> visited;
bool dfs(char a,char b)
{if (a==b)
    return true;
    visited[a]=true;
    bool ans= false;
    for(auto ngh : l[a])
    {
        if(ngh==b)
        return true;
         ans = dfs(ngh,b);
         if(ans== true)
         return ans;
    }
    return false;
    
}
    
};

int main() {
    int p;
    cin>>p;
    while(p--)
    {
        string s,t;
        cin>>s;
        cin>>t;
        int m;
        cin>>m;
        Graph g;
        int i ;
        while(m--)
        {char x,y,w,z;
            cin>>x>>w>>z>>y;
           // cout<<x<<" "<<y;
            g.addedge(x,y);
        }
        bool possible= false;
        if(s.length()==t.length())
        { bool found=false;
            for( i =0;i<s.length();i++)
        { bool found = g.dfs(s[i],t[i]);
        if(found== false)
        break;
            
        }
        if(i==s.length())  
        {possible=true;}
        } 
        if(possible)
        {cout<<"YES"<<endl;}
        else cout<<"NO"<<endl;
    }
	// your code goes here
	return 0;
}
2

Your program seems indeed too slow: the strings can be of length 1000, and for each character you are running a DFS that might need to traverse 1000 edges. Example, if you have a graph with edges like:

a->b
a->b
a->b
b->c
b->c
c->d
…
x->y
y->z

and strings:
aaaaaaaaaaaaaaaaaaaaaaaaaa…(length 1000)
zzzzzzzzzzzzzzzzzzzzzzzzzzzzzzz…(length 1000)

That would probably take a good amount of time, and that’s just 1 of 1000 testcases.

1 Like