Author Arunima Mandal

SPOJ – EZDIJKST – Easy Dijkstra Problem

Arunima Mandal Leave a comment

Problem: https://www.spoj.com/problems/EZDIJKST/

Note: This is a pretty straightforward problem of basic Dijkstra implementation.

In case of the Wrong Answer:

  1. Notice that the input is a Directed graph, not an undirected graph. Take care of it while creating the adjacency matrix of the graph.
  2. Notice that while pushing in the priority queue, you should push the updated cost of the current node as the first element of the pair and then the node itself as the 2nd element of the pair.

In case of the Time Limit Exceeded:

The funny thing in my case is, I got the time limit exceeded because I declared the Dijkstra function as int but was not returning any integer at first, instead I was directly printing the output inside that function. I had no idea that this fault can result in a “time limit exceeded” verdict. As I didn’t notice that at first, I debugged the code for so much time, and lastly noticed that the return type of the function should be void as I was not returning anything there. That fix made my code Accepted in SPOJ! Later, I kept the function type as int and returned the result from there.

Code:

#include <bits/stdc++.h>

#define INF             INT_MAX
#define MAX             10004
#define pii             pair<int,int>

using namespace std;

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    dis[src]=0;

    priority_queue<pii, vector<pii>, greater<pii> >pq;
    pq.push({0, src}); // Insert source in priority queue and initialize its distance as 0.

    while(!pq.empty())
    {
        int u=pq.top().second;
        int cost=pq.top().first;
        pq.pop();

        //Optimization in priority queue:
        //Since the pq can hold same node more than once with different costs,
        //no need to process the nodes which has already been updated to shorter distance
        if(dis[u]<cost) continue;

        for(int i=0; i<adj[u].size(); i++)
        {
            int v=adj[u][i].first;
            cost=adj[u][i].second;

            if(dis[v]>dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
                pq.push({dis[v], v});
            }
        }
    }
    return dis[dst];
}

int main()
{
    ///freopen("in.txt","r",stdin);
    ///freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int node,edge;
        cin>>node>>edge;

        vector<vector<pair<int,int> > > adj(MAX);

        for(int i=0; i<edge; i++)
        {
            int from,to,cost;
            cin>>from>>to>>cost;
            adj[from].push_back({to, cost});
            //adj[to].push_back({from, cost}); //If undirected graph
        }

        int src,dst;
        cin>>src>>dst;

        int min_distace=dijkstra(src, dst, adj);

        if(min_distace==INF) cout<<"NO"<<endl;
        else cout<<min_distace<<endl;
    }
    return 0;
}

LeetCode 211. Design Add and Search Words Data Structure

Arunima Mandal Leave a comment

Problem Link: https://leetcode.com/problems/design-add-and-search-words-data-structure/description/

Note: This problem involves an amazing application of Trie. The “.” in the problem statement gives a twist to the problem.

Code:

class WordDictionary {
public:
    struct TrieNode
    {
        TrieNode *child[26]={};
        bool w=0;
    };
    TrieNode *root=new TrieNode();
    WordDictionary() {
        
    }
    
    void addWord(string word) {
        TrieNode *it=root;
        for(int i=0; i<word.size(); i++)
        {
            int ind=word[i]-'a';
            if(!it->child[ind]) it->child[ind]=new TrieNode();
            it=it->child[ind];
        }
        it->w=1;
    }
    bool search(string word)
    {
        return search(root, word);
    }
    
    bool search(TrieNode *it, string word) {
        for(int i=0; i<word.size() && it; i++)
        {
            if(word[i]!='.')
            {
                int ind=word[i]-'a';
                if(!it->child[ind]) return false;
                it=it->child[ind];   
            }
            else
            {
                string s=word.substr(i+1);
                TrieNode *tmp=it;
                for(int j=0; j<26; j++)
                {
                    it=tmp->child[j];
                    if(search(it, s)) return true;
                }
            }
        }
        return it && it->w; //covers the case when the it is null, and that happens only when going from . to any other character which doesn't exist.
    }
};

/**
 * Your WordDictionary object will be instantiated and called as such:
 * WordDictionary* obj = new WordDictionary();
 * obj->addWord(word);
 * bool param_2 = obj->search(word);
 */

SPOJ – PHONELST – Phone List

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/PHONELST/


Solution: This is a pretty great problem regarding applying Trie in the case of a numerical string. If your code is not executing, please take a good look at whether you are taking the index as s[i]-‘0’ instead of s[i]-‘a’. Since in most cases, the strings consist of alphabets, so in most cases in the Trie code template, we can write the index code as s[i]-‘a’ habitually.

Here the main trick is to sort the vector containing strings before inserting those into the Trie, to make sure we are marking the smaller words first. Otherwise, we will miss the smaller words, and that way the long words with the same prefix equal to the smaller words will go undetected.

Code:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode
{
    TrieNode *child[10]={};
    bool word=0;
};

bool insert(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'0';
        if(it->word==1) return 0;
        if(!it->child[ind]) it->child[ind]= new TrieNode();
        it=it->child[ind];
    }
    it->word=1;
    return 1;
}

int main()
{
    int t,n;
    cin>>t;
    for(int z=0; z<t; z++)
    {
        int n;
        cin>>n;
        vector<string> v;
        string s;
        for(int i=0; i<n; i++)
        {
            cin>>s;
            v.push_back(s);
        }
        sort(v.begin(), v.end());

        TrieNode *root=new TrieNode();
        bool is_consistent=1;
        for(int i=0; i<n && is_consistent; i++)
        {
            is_consistent=insert(root, v[i]);
        }

        if(is_consistent) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

SPOJ – ADAINDEX – Ada and Indexing

Arunima Mandal Leave a comment

Problem Link: https://www.spoj.com/problems/ADAINDEX/

Note: The idea behind the problem is pretty simple. Just keep a count variable in each node while building the Trie, so that each node keeps track of its count in how many words it has been repeated.

Solution:

#include <bits/stdc++.h>

using namespace std;

struct TrieNode
{
    TrieNode *child[26]={};
    int cnt=0;
};

void insert(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'a';
        if(!it->child[ind]) it->child[ind]= new TrieNode();
        it=it->child[ind];
        it->cnt++;
    }
}

int search(TrieNode *root, string s)
{
    TrieNode *it=root;
    for(int i=0; i<s.size(); i++)
    {
        int ind=s[i]-'a';
        if(!it->child[ind]) return 0;
        it=it->child[ind];
    }
    return it->cnt;
}

int main()
{
    int n,q;
    cin>>n>>q;
    TrieNode *root=new TrieNode();
    for(int i=0; i<n; i++)
    {
        string s;
        cin>>s;
        insert(root, s);
    }

    for(int i=0; i<q; i++)
    {
        string s;
        cin>>s;
        cout<<search(root, s)<<endl;
    }
    return 0;
}

LeetCode 648. Replace Words

Arunima Mandal Leave a comment

Problem: https://leetcode.com/problems/replace-words/description/

Solution:

The intuition to the problem is pretty simple.

  • Build the trie data structure by inserting all the words from the dictionary.
  • Go through the sentence, take each word(separated by space), and search in the trie for the root in that word.
    1. If the root is found (trie naturally ensures the shortest length root), then stop and return the index so that we can take that as the substring.
    2. Otherwise, we have to take the entire word, so return the total length of the word we were considering.

Complexity:

  • Time complexity:

O(n) where n is the length of the sentence.

  • Space complexity:

O(n) where n is the size of our trie data structure.

Code:

class Solution {
public:
    struct TrieNode{
        TrieNode *child[26]={};
        bool end=0;
    };
    void insert(TrieNode *root, string s)
    {
        TrieNode *it=root;
        for(int i=0; i<s.size(); i++)
        {
            int ind=s[i]-'a';
            if(!it->child[ind]) it->child[ind]=new TrieNode();
            it=it->child[ind];
        }
        it->end=1;
    }
    int search(TrieNode *root, string s)
    {
        TrieNode *it=root;
        bool found=0;
        for(int i=0; i<s.size(); i++)
        {
            int ind=s[i]-'a';
            if(!it->child[ind]) break; //didn't find any root
            it=it->child[ind];
            if(it->end==1) return i+1;
        }
        return s.size(); 
    }
    string replaceWords(vector<string>& dictionary, string sentence) {
        TrieNode *root=new TrieNode();
        for(int i=0; i<dictionary.size(); i++)
        {
            insert(root, dictionary[i]);
        }
        string ans="",s="";
        for(int i=0; i<sentence.size(); i++)
        {
            if(sentence[i]==' ') 
            {
                int x=search(root, s);
                ans+=s.substr(0,x);
                ans+=" ";
                s.clear();
            }
            else s+=sentence[i];
        }
        int x=search(root, s); //for last word of the sentence
        ans+=s.substr(0,x);
        return ans;
    }
};