Category Uncategorized

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

UVa – 10986 – Sending email

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/109/10986.pdf

Note: This problem is a straightforward application of the standard Dijkstra algorithm.

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;

int dijkstra(int src, int dst, vector<vector<pii>> &adj)
{
    vector<int> dis(MAX, INF);
    //dis[100005]={INT_MAX} ; why doesn't work(gives wrong answer) I don't know!
    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});
            }
        }
    }
    return dis[dst];
}

int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);
    int t;
    cin>>t;
    for(int z=1; z<=t; z++)
    {
        int node,edge,src,dst;
        cin>>node>>edge>>src>>dst;
        if(edge==0)
        {
            cout<<"Case #"<<z<<": unreachable"<<endl;
            continue;
        }

        vector<vector<pair<int,int> > > adj(node+1);
        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 min_distace=dijkstra(src, dst, adj);
        if(min_distace!=INT_MAX)
        {
            cout<<"Case #"<<z<<": "<<min_distace<<endl;
        }
        else
        {
            cout<<"Case #"<<z<<": unreachable"<<endl;
        }
    }
    return 0;
}