Page 3 of 66

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

UVa – 1112 – Mice and Maze

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/11/1112.pdf

Note:

Though the problem gives the vibe of a 2D Dijkstra as it is about the cells, after reading about the input format and after seeing the sample input, it can be understood that it is a straightforward 1D application of Dijkstra.

And about the input format, we do not have to bother with the blank lines because “std::cin” by nature isn’t bothered with those blank lines. You can follow this link for more added knowledge on this.

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;
    while(t--)
    {
        int node, dst, end_time;
        cin>>node>>dst>>end_time;

        int edge;
        cin>>edge;
        vector<vector<pair<int,int> > > adj(node+1);

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

        int ans=0;
        for(int i=1; i<=node; i++)
        {
            int src=i;
            int min_distace=dijkstra(src, dst, adj);
            if(min_distace<=end_time) ans++;
        }
        cout<<ans<<endl;
        if(t>0) cout<<endl;
    }


    return 0;
}

UVa – 11690 – Money Matters

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/external/116/11690.pdf

Note: This is a slight variation of the problem UVa – 10608 – Friends. Aside from figuring out that we need each node’s actual root (to determine each separate collection) as in the UVa 10608, we need to figure out how to calculate the money owes and money owed.

Ultimately, people in the same group or collection can make an exchange with one another. For example, for the test case,

4 2 //n=4, m=2
15
20
-10
-25
0 2
1 3
1 2

So initially, money_owe[]={15, 20, -10, -25}

Here, for Union(0, 2), 0 can give money to 2, then money_owe[] would be: money_owe[]={5, 20, 0, -25}.

Then for(1, 3), 1 can give money to 3, then money_owe[] would be: money_owe[]={5, 0, 0, -5}.

Here, for Union(1, 2), 1 can give money to 2, then money_owe[] would be: money_owe[]={5, 0, 0, -5}.

Notice that, for the last pair, nothing changes as none of them owes or is owed money. But just for this pair, each of the people has become 1 single group. Without this pair, the output of the problem would be “IMPOSSIBLE”. But since our example input has this pair, so all people are Friends, so they can share money. Hence, person 0 and person 3 can exchange money even though they are not directly connected.

In summary, we just need to check every group’s total sum. If the sum for any single group is not equal to 0, then we can immediately say that it is IMPOSSIBLE.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(x==root[x]) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(ranking[rootX]>=ranking[rootY])
        {
            root[rootY]=rootX;
            ranking[rootX]+=ranking[rootY];
        }
        else
        {
            root[rootX]=rootY;
            ranking[rootY]+=ranking[rootX];
        }
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int t;
    cin>>t;
    while(t--)
    {
        int n,m;
        cin>>n>>m;

        vector<int> root(n), ranking(n);
        int money_owe[n];

        for(int i=0; i<n; i++)
        {
            root[i]=i;
            ranking[i]=1;

            int money;
            cin>>money;
            money_owe[i]=money;
        }

        for(int i=0; i<m; i++)
        {
            int x,y;
            cin>>x>>y;
            Union(x, y, root, ranking);
        }

        vector<vector<int> > members(n);
        for(int i=0; i<n; i++)
        {
              int root_i=Find(i, root);  //updating the final root vector
              members[root_i].push_back(i);
        }
        bool f;
        for(int i=0; i<n; i++)
        {
            int sum=0;
            for(int j=0; j<members[i].size(); j++)
            {
                sum+=money_owe[members[i][j]]; // the sum of money should be 0 within a group
            }

            f=0;
            if(sum!=0)
            {
                cout<<"IMPOSSIBLE"<<endl;
                f=1;
                break;
            }
        }
        if(!f)cout<<"POSSIBLE"<<endl;
    }
    return 0;
}

UVa – 10685 – Nature

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/external/106/10685.pdf

Note: This problem is the basic application of the Union-Find algorithm. With the slight input manipulation, it is actually pretty similar to the problem UVa – 10608 – Friends. Just like that problem, this problem can be solved with approach 2 mentioned in the “Friends” problem, but I prefer approach 1.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(x==root[x]) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(ranking[rootX]>=ranking[rootY])
        {
            root[rootY]=rootX;
            ranking[rootX]+=ranking[rootY];
        }
        else
        {
            root[rootX]=rootY;
            ranking[rootY]+=ranking[rootX];
        }
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int n,m;
    while(cin>>n>>m)
    {
        if(n==0 && m==0) break;

        vector<int> root(n), ranking(n);
        unordered_map<string,int> ump;
        int c=0;
        for(int i=0; i<n; i++)
        {
            root[i]=i;
            ranking[i]=1;

            string s;
            cin>>s;
            ump[s]=c;
            c++;
        }

        for(int i=0; i<m; i++)
        {
            string s1, s2;
            cin>>s1>>s2;
            Union(ump[s1], ump[s2], root, ranking);
        }

        int ans=-1;
        for(int i=0; i<n; i++)
        {
            ans=max(ranking[i], ans);
        }
        cout<<ans<<endl;
    }
    return 0;
}

UVa – 11966 – Galactic Bonding

Arunima Mandal 1 Comment

Problem Link: https://onlinejudge.org/external/119/11966.pdf

Note: This problem is the basic implementation of the Union-Find problem.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(x==root[x]) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(ranking[rootX]>=ranking[rootY])
        {
            root[rootY]=rootX;
            ranking[rootX]+=ranking[rootY];
        }
        else
        {
            root[rootX]=rootY;
            ranking[rootY]+=ranking[rootX];
        }
    }
}

int main()
{
//    freopen("in.txt", "r", stdin);
//    freopen("out.txt", "w", stdout);
    int t;
    cin>>t;
    for(int z=1; z<=t; z++)
    {
        int n;
        double d;
        cin>>n>>d;
        vector<int> root(n), ranking(n);

        for(int i=0; i<n; i++)
        {
            root[i]=i;
            ranking[i]=1;
        }

        vector<pair<double, double> > v;
        for(int i=0; i<n; i++)
        {
            double x,y;
            cin>>x>>y;
            v.push_back({x,y});
        }

        for(int i=0; i<n-1; i++)
        {
            double x1=v[i].first;
            double y1=v[i].second;
            for(int j=i+1; j<n; j++)
            {
                double x2=v[j].first;
                double y2=v[j].second;
                double dis=sqrt((x2-x1)*(x2-x1) + (y2-y1)*(y2-y1)); //General formula of distance between two points on a 2D plane
                if(dis<=d) Union(i, j , root, ranking);
            }
        }

        int ans=0;
        for(int i=0; i<n; i++)
        {
            if(root[i]==i) ans++;
        }
        cout<<"Case "<<z<<": "<<ans<<endl;
    }
    return 0;
}