Help needed (for ACM14KG3 Discount on crackers)

Link to the question:
https://www.codechef.com/LRNDSA08/problems/ACM14KG3
My logic:
form the graph with given mappings.
find all the strongly connected components(used Kosaraju’s algo) and make a compressed graph…
after that I’m doing a dfs from nodes which have degree = 1(in compressed graph)
noting down the in and out time for all nodes…
now going through the strings if the corresponding character at a index belong to same connected component then i can make a move…or else if the first character’s node is an ancestor of the other…then YES or else it’s not possible…
Saw the editorial…I know i have over killed the problem… But it will be really helpful for me if i can know where my code is going wrong…
ps : found the problem…it was while checking if there’s a path from one node to another in the condensed graph using in and out time…solved the problem by just doing a dfs in the condensed graph and checking for reachability .
@everule1 Can some one tell me how to efficiently check for reachability in an directed graph with just one dfs or bfs?

#include<bits/stdc++.h> 
#define lld      long long
#define mp       make_pair
#define pb       push_back
#define ff       first
#define ss       second
#define pii      pair<int,int>
#define vii      vector<int>
#define umap     unordered_map
#define lb       lower_bound
#define ub       upper_bound
#define mod      1000000007
#define all(x)   x.begin(),x.end()
#define sort1(x) sort(x,greater<int>())
#define fio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
using namespace std;

namespace forever {
    template<class type1,class type2>
        inline istream &operator>>(istream &in,pair<type1,type2> &p)
        {
            in>>p.ff>>p.ss;
            return in;
        }
    template<class type1,class type2>
        inline ostream &operator<<(ostream &o,pair<type1,type2> &p)
        {
             o<<p.ff<<" "<<p.ss;
            return o;
        } 
    template<class type>
        inline ostream &operator<<(ostream &o,vector<type> &v)
        {
            for(int i=0;i<v.size();i++)
                o<<v[i]<<" ";
            return o;    
        }
    template<class type>
        inline ostream &operator<<(ostream &o,set<type> &v)
        {
            for(int x: v)
                o<<x<<" ";
            return o;    
        }        
    template<class t>
        inline istream &operator>>(istream &in,vector<t> &p)
        {
            for(auto & x : p)
                in >> x;
            return in;
        }
        
    int power(int x, int y,int p = mod) {  
        int res = 1;
        x = x % p; 
        while (y > 0) {
            if (y & 1)  
                res = (res*x) % p;  
            y = y>>1;
            x = (x*x) % p;  
        }  
        return res;  
    }    
    struct custom_hash {
	    static uint64_t splitmix64(uint64_t x) {
		    x += 0x9e3779b97f4a7c15;
		    x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
		    x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
		    return x ^ (x >> 31);
	    }

	    size_t operator()(pair<uint64_t,uint64_t> x) const {
		    static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
		    return splitmix64(x.first + FIXED_RANDOM)^(splitmix64(x.second +     FIXED_RANDOM) >> 1);
	    }
	    size_t operator()(uint64_t x) const {
            static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
            return splitmix64(x + FIXED_RANDOM);
        }
    };
}
using namespace forever;

vii adj[26] , rev[26] , compressed[26];
umap<int,bool,custom_hash> seen;
vii comp(26),in(26),out(26);

void dfs1(int v,stack<int> &s){
    seen[v] = true;
    for(int x: adj[v]){
        if(!seen[x]){
            dfs1(x,s);
        }
    }
    s.push(v);
}

void dfs2(int v,int cc) {
    seen[v] = true;
    comp[v] = cc;
    //cout << v << "  ";
    for(int x: rev[v]){
        if(!seen[x]){
            dfs2(x,cc);
        }
    }
}

void dfs3(int v,int& t){
    in[v] = t++;
    seen[v] = true;
    for(int x: compressed[v]){
        if(!seen[x])
            dfs3(x,t);
    }
    out[v] = t++;
}

void init() {
    for(int i=0;i<26;i++){
        adj[i].clear();
        rev[i].clear();
        compressed[i].clear();
    }
    seen.clear();
    comp.clear();
    in.clear();
    out.clear();
}

void test_cases(){
    //cout << "********new tc*********\n";
    string a,b;
    int m,i;
    cin >> a >> b >> m;
    init();
    
    while(m--){
        string str;
        cin >> str;
        adj[str[0]-'a'].pb(str[3]-'a');
        rev[str[3]-'a'].pb(str[0]-'a');
    }
    
    int nn = a.length() , mm = b.length();
    if(nn!=mm){
        cout << "NO\n";
        return;
    }
    
    stack<int> s;
    for(i=0;i<26;i++){
        if(!seen[i] && adj[i].size() > 0){
            dfs1(i,s);
        }
    }
    seen.clear();
    //cout << "$$$$$$$$$$$$$$$$$$$$$$\n";
    int cnt = 0;
    while(!s.empty()) {
        int te = s.top();
        s.pop();
        if(!seen[te]){
            cnt++;
            dfs2(te,cnt);
            //cout << "\n";
        }
    }
    //cout << "****************************\n";
    for(i=0;i<26;i++){
        if(adj[i].size() == 0)
            continue;
        int te = comp[i];    
        for(int x: adj[i]){
            if(comp[x] != te){
                compressed[te].pb(comp[x]);
            }
        }
    }
    //cout << compressed << "\n";
    seen.clear();
    //cout << "heyyyyyyyyyy*****\n";
    int ti = 0;
    for(i=1;i<=cnt;i++){
        if(!seen[i] && compressed[i].size()==1){
            dfs3(i,ti);
        }
    }
    //cout << "hiii**\n";
    bool can = true;
    for(i=0;i<nn;i++){
        if(comp[a[i]-'a'] != comp[b[i]-'a']){
            // if the characters belong to two different s.c.components then 
            // comp[a[i]] ---> comp[b[i]] path should exist
            int sr = comp[a[i]-'a'];
            int rs = comp[b[i]-'a'];
            can &= (in[sr] < in[rs] && out[sr] > out[rs]);
        }
    }
    if(can)
        cout << "YES\n";
    else
        cout << "NO\n";
}
int32_t main()
{
    fio;     
    #ifndef ONLINE_JUDGE 
    freopen("sip.txt","r",stdin);
    freopen("sout.txt","w",stdout);
    #endif
    
    int t=1;
    cin >> t;
    while(t--){
        test_cases();
    }
    
    return 0;
}
    vector<int> adj(26);
    while(m--){
        string path;
        cin>>path;
        adj[path[0] - 'a']|=(1<<(path[3]-'a'));
    }
    for(int i=0;i<26;i++){
        adj[i]|=(1<<i);
    }
    for(int k=0;k<26;k++){
        for(int i=0;i<26;i++){
            if((adj[i]&(1<<k))){
                adj[i]|=adj[k];
            }
        }
    }

I don’t think there’s a better way than this. It doesn’t seem doable in less than O(|E||V| + |V|^2)(DFS all nodes) even though it should. Mine is O(|V|^3/32)
@galencolin Can you think of an O(|V|^2 + |E|) algorithm for this?

2 Likes

See # 1 here to improve your bitset solution.

This graph only has 26 nodes, so I don’t see why anything efficient is necessary, but it seems like OP’s solution should be correct (albeit maybe bugged) for some O(|V| + |E|) SCC magic. I think the issue @sriram1012 is that you should start your DFS only from “root” nodes of the “directed trees” in the compressed graph, that is, those with indegree 0.

1 Like

Why have I gotten the “First Mention” badge twice

Thanks I understood it now.

1 Like

yeah i found the mistake and corrected it…
i thought by compressing the graph it will be easy to find if one node is reachable from other or not just by analysing their in and out times just like how we can do it for an undirected graph…so that the whole solution can run in O(n + e) time…But i found a contradicting case where the in and out time are meaningless…
for example, a—> b <—c
so here i cannot determine if b is reachable from a and c simulatenously…as i can only assign a single number for in and out time…
Can you suggest me a good approach for checking for reachability in a directed graph ( which requires only one dfs or bfs) ?
it may not be useful for this problem but for a similar modified problem like :
To check if a sequence A(size <= 10^5) can be converted to B using a transition graph…So in that case even the modified floyyd warshall solution(as given by @everule1) will get TLE…
BTW thanks for replying @everule1 @galencolin

You’re right. And after looking at some research papers, it doesn’t seem possible to construct a universally efficient solution :frowning:

Oh okay…
thank you so much for spending your time :slightly_smiling_face: :slight_smile:

what’s wrong in this solution , can anyone give test cases for which this solution fails @sriram1012 @galencolin @everule1

    bool **connect = new bool*[26];
	for (int i = 0; i < 26; i++) {
		connect[i] = new bool[26];
		for (int j = 0; j < 26; j++) {
			connect[i][j] = false;
		}
	}
	int m;
	cin >> m;
	rep_i(0, m) {
		string maping;
		cin >> maping;
		connect[maping[0] - 'a'][maping[3] - 'a'] = true;
	}
	bool flag = true;
	if (s.length() == t.length()) {
		for (int i = 0; i < s.length(); i++) {
			if (s[i] == t[i]) continue;
			if (connect[s[i] - 'a'][t[i] - 'a'] == false) {
				flag = false;
				break;
			}
		}
		// cout << ans << endl;
	} else {
		flag = false;
	}
	if (flag) {
		cout << "YES";
	} else {
		cout << "NO";
	}
	 cout << endl;

	for (int i = 0; i < 26; i++)
		delete connect[i];
	delete []connect;

I haven’t tested, but are you connecting i->i by default(No change)?

here i maintain a adjacency matrix which stores true if there is path from a->b
next in iteration if s[i]!=t[i] then i am checking if we can map s[i]->t[i] if not then i break the loop
print “No” else print “Yes”

You didn’t consider the possibility of having a path(of len >=2) from one node to other…
for example: a–> b --> c
in this case there’s a path from a to c via b…your code won’t consider that.

1 Like

Thanx @sriram1012 I got it, i was considering only one mapping😅