Author Arunima Mandal

UVa – 200 – Rare Order

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/2/200.pdf

Note: I think the problem statement was very much unclear. The important thing to notice is that it is explicitly mentioned in the input section that the string will be ordered. So you cannot change the order of the string.

Now, the problem actually demands printing unique characters column wise maintaining that each character you are printing cannot be printed twice. So simply put – “print unique characters of the ordered strings by column-wise traversal”.

For example, for the input:

XYZ

ZUX

XWV

#

So in the 1st column, there are XZX, where X is repeated, so we get XZ from this column.

in the 2nd column, there is YUW, where no character was found before, all are new, so we get YUW from this column.

In the 3rd column, there are ZXZ, here both X and Z already exist in our finding, only V is new, so we get V from this column.

At the end of the traversal, by concatenating all column’s results, we have XZYUWV – which is the output.

I have solved this using the above brute force method, so no DFS or Topological Sort is needed here if time is a concern.

**We’ll have to keep in mind that, all string sizes may not be the same. So we’ll have to take care of that while traversing and accessing elements.

**For the first time, the output of UDebug’s test cases’ output didn’t match up with mine (but this code was accepted by the UVa) which means that the UDebug test cases are wrong because the output was supposed to be unique as per my understanding. If that is not the case not, please let me know in the comments. Thanks!

Code:

#include <bits/stdc++.h>

using namespace std;

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    vector<string> v;
    int maxi=INT_MIN;
    string s;
    while(cin>>s)
    {
        if(s!="#")
        {
            v.push_back(s);
            maxi=(maxi, s.size());
        }
        else
        {
            unordered_map<char,int> visited;
            for(int j=0; j<maxi; j++)
            {
                for(int i=0; i<v.size(); i++)
                {
                    string ss=v[i];
                    if(j<ss.size() && !visited.count(ss[j]))
                    {
                        cout<<ss[j];
                        visited[ss[j]]=1;
                    }
                }
            }
            cout<<endl;
            v.clear();
            maxi=INT_MIN;
        }
    }
    return 0;
}

UVa – 11060 – Beverages

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/110/11060.pdf

Note: This problem can be solved using basic topological sort but with a simple tweak to maintain the order required in the problem statement. I used a priority queue to maintain the ascending order of the nodes that have indegree 0.

Code:

#include <bits/stdc++.h>

using namespace std;


vector<int> topSort(int node, vector<int> &indeg, vector<vector<int> > &adj)
{
    vector<int> ans;
    priority_queue<int, vector<int>,  greater<int > > pq;

    for(int i=0; i<node; i++)
    {
        if(indeg[i]==0) pq.push(i);
    }

    while(!pq.empty())
    {
        int u=pq.top();
        pq.pop();
        ans.push_back(u);
        for(int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j];
            indeg[v]--;
            if(indeg[v]==0) pq.push(v);
        }
    }
    return ans;
}


int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    int z=1;
    int node,edge;
    while(cin>>node)
    {
        unordered_map<string,int> mp1;
        unordered_map<int,string> mp2;
        int c=0;
        for(int i=0; i<node; i++)
        {
            string s;
            cin>>s;
            mp1[s]=c;
            mp2[c]=s;
            c++;
        }

        cin>>edge;
        vector<vector<int> > adj(node);
        vector<int> indeg(node,0);

        for(int i=0; i<edge; i++)
        {
            string from,to;
            cin>>from>>to;
            adj[mp1[from]].push_back(mp1[to]);
            indeg[mp1[to]]++;
        }

        vector<int> ans=topSort(node, indeg, adj);

        cout<<"Case #"<<z<<": Dilbert should drink beverages in this order:";

        for(int i=0; i<ans.size(); i++)
        {
            cout<<" "<<mp2[ans[i]];
        }
        cout<<"."<<endl<<endl;
        z++;
    }
    return 0;
}

UVa – 10449 – Traffic

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/104/10449.pdf

Note: The fact that this problem falls under the Bellman-Ford – is the key point here. Because the amount the city authority gets is the subtraction of two integers can produce negative integers. And cubing them will definitely not change the sign of the result(which square would have done instead). Once you can figure out this, The problem is a straightforward implementation of the Bellman-Ford algorithm.

As a side note, I was getting the wrong answer repeatedly even if my code was passing all the test cases of UDebug. Then after changing the data type of the “dis” vector from int to long long int made the code “accepted” finally on the UVa online judge!

Code:

#include <bits/stdc++.h>

#define pii             pair<int, int>


/*---------------------------Graph Moves-----------------------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------------------------*/

using namespace std;

vector<long long int> bellman_ford(int node, int edge, vector<pair<pii, int> > &adj)
{
    vector<long long int> dis(node+1, INT_MAX);
    dis[1]=0;

    for(int i=0; i<node; i++)
    {
        for(int j=0; j<edge; j++)
        {
            int u=adj[j].first.first;
            int v=adj[j].first.second;
            int cost=adj[j].second;
            if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
            {
                dis[v]=dis[u]+cost;
            }
        }
    }
    //Running an extra loop to find out whether the graph contains any negative cycle loop or not
    for(int j=0; j<edge; j++)
    {
        int u=adj[j].first.first;
        int v=adj[j].first.second;
        int cost=adj[j].second;
        if(dis[u] != INT_MAX && dis[v] > dis[u]+cost)
        {
            dis[v]=INT_MAX; //Marking the nodes which will keep decreasing infinitly due to negative weight cycle
        }
    }
    return dis;
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);


    int t=0, node, edge;
    while(cin>>node)
    {
        vector<int> busyness(node+1);
        for(int i=1; i<=node; i++)
        {
            cin>>busyness[i];
        }
        cin>>edge;
        vector<pair<pii, int> > adj;
        for(int i=0; i<edge; i++)
        {
            int from,to,w,cost;
            cin>>from>>to;

            w=busyness[to]-busyness[from];
            cost=w*w*w;
            adj.push_back({{from, to}, cost});
        }

        vector<long long int> dis=bellman_ford(node, edge, adj);

        int q, dst;
        cin>>q;
        cout<<"Set #"<<++t<<endl;

        for(int i=0; i<q; i++)
        {
            cin>>dst;
            if(dis[dst]<3 || dis[dst]==INT_MAX)
            {
                cout<<"?"<<endl;
            }
            else
            {
                cout<<dis[dst]<<endl;
            }
        }
    }
    return 0;
}

UVa – 12878 – Flowery Trails

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/128/12878.pdf

Note: After reading this problem, the first intuition that should come is we’ll need the exact path each shortest distance is taking. We cannot count any edge leading to the shortest path more than once.

I followed that intuition and so took a 2D vector named parent which will mainly contain the parent of each node leading to the destination node. I have kept the length info too in the parent vector to use that later while summing up the total value of lengths.

So this problem is using basic Dijkstra, only with a tweak in the approach. Here the tweak I used is in updating the parent vector properly which is containing all the routes that lead to the shortest distance. And later only traversing the parent vector to collect the sum of all shortest paths.

Code:

#include <bits/stdc++.h>

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

/*----------------------Graph Moves----------------*/
//const int fx[]={+1,-1,+0,+0};
//const int fy[]={+0,+0,+1,-1};
//const int fx[]={+0,+0,+1,-1,-1,+1,-1,+1};   // Kings Move
//const int fy[]={-1,+1,+0,+0,+1,+1,-1,-1};  // Kings Move
//const int fx[]={-2, -2, -1, -1,  1,  1,  2,  2};  // Knights Move
//const int fy[]={-1,  1, -2,  2, -2,  2, -1,  1}; // Knights Move
/*------------------------------------------------*/

using namespace std;


void dijkstra(int src, int dst, vector<vector<pii>> &adj, vector<vector<pii>> &parent)
{
    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 the priority queue:
        /*
        Ideally, for updating the priority queue, we must delete the old value and reinsert with the
        new cost value. But, as we know that the updated cost value is always lesser than the old
        value and would be popped from the queue and visited before the old value,
        we could save time and avoid removing the old value from the queue.
        */
        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});
                parent[v].clear();
                parent[v].push_back({cost, u});
            }
            else if(dis[v]==dis[u]+cost)
            {
                parent[v].push_back({cost, u});
            }
        }
    }
}


int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    int node, edge;
    while(cin>>node>>edge)
    {
        vector<vector<pii> > adj(node);
        //vector<pair<int,int>> adj[node]; //can also be written like this

        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});
        }

        int src=0, dst=node-1;
        vector<vector<pii> > parent(node);

        dijkstra(src, dst, adj, parent);

        queue<int> q;
        q.push(node-1);
        int ans=0;
        vector<int> vis(node,0);
        while(!q.empty())
        {
            int u=q.front();
            q.pop();
            if(vis[u]) continue;
            vis[u]=1;
            for(int i=0; i<parent[u].size(); i++)
            {
                ans+=parent[u][i].first;
                q.push(parent[u][i].second);
            }
        }
        cout<<ans*2<<endl;
    }
    return 0;
}

Why we must use getchar() immediately before using getline() if std::cin or scanf() statements are present before the getline():

Arunima Mandal 4 Comments

Some important factors to know before the explanation:

  1. getline() reads input until the delimiter (default delimiter is the newline (“\n”)) character is found.
  2. getline removes the delimiter from the input buffer, std::cin or scanf does not.
  3. cin discards any other character present on the input buffer and takes the input only as new in the input buffer. That’s why while using cin after another cin, even when the previous cin leaves a newline in the input buffer, the later cin doesn’t get bothered with that.

So when a user takes any input using std::cin/ scanf(), they hit enter, which is actually a ‘\n’ char. cin leaves this “\n” in the input buffer. Then if you use getline, getline will only read that “\n” in the input buffer (instead of the string you want) and skip to next line. So the program seems to skip over the whole getline() command since newline (‘\n’) is the by-default delimiter for getline() and it immediately stops taking any more characters as input (alongside removing the delimiter itself from the input buffer).

So to solve this problem, we use getchar() or std::cin.ignore(1000,’\n’).

  1. getchar(): Before using getline(),The getchar() is used to read the character(after using cin/scanf) which is a “new line” (“\n”) and which wasn’t removed from the input-buffer by the cin/scanf.
  2. cin.ignore(100,’\n’): We use cin.ignore(100,’\n’) to clear the buffer up to the string that you want. In this syntax, The “1000” means to skip over a specific number of chars(in this case 100 chars) before the specified delimiter(in this case, the newline character)