UVa – 11690 – Money Matters

Arunima Mandal

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

One thought on “UVa – 11690 – Money Matters”

  1. Pingback: Disjoint Set/ Union Find (Union by Rank + Path Compression) | Fall out, Codes!

Leave a comment