# CF - Global Round 6 - Problem D - Decreasing Debts

I had one doubt in Codeforces Global Round 6 - Problem D - Decreasing Debts

I’m using the splitwise and two pointer approach to solve it.

Here is my solution.

``````/*
Author : SummerPark ~ 2019
*/

#include <bits/stdc++.h>
using namespace std;

// Custom Comparator
bool mycomp(pair<long long  int ,long long int > a, pair<long long  int ,long long int > b){
if(a.second != b.second)
return a.second > b.second;

return a.first < b.first;
}

int main(){
/*

So here's what my solution approach is,

Say a person has to give X money and take Y money. His net exchange amount would
involve only one of the two actions, think about it!

if X is bigger, then it means he has to give more money than take, so we can
substitute everything by the statement "he has to give (X-Y) Money. it's the same

So what we'll do, is we will calculate net exchange amount for all persons.

Then we'll pick two person with maximum amount to give and maximum amount to take.

Lets call the person with maximum amount to give as Person 1, and person with
maximum amount to take as Person 2.

Now let's just say that Person 1 has to give amount_1, and Person 2 has to take
amount_2.

There are 3 Possibility from here.

1. If amount_1 is equal to amount_2

Well then we'll simply settle both of them and move to the next persons in line.

2. If amount_1 is less than amount_2

Then we'll settle everthing for Person 1 as he has given what he had to give, but
the Person 2 hasn't taken all he had to take. So we'll move to the next giver in
the line

3. If amount_2 is less than amount_1

Then we'll settle everthing for Person 2 as he has taken what he had to take, but
the Person 1 hasn't given all he had to give. So we'll move to the next taker in
the line.

We'll store all the result all the transaction and output them in the end.

*/

// So let the hacking begin!  :P

// We Input n and m.
long long int n,m;cin>>n>>m;

// I am making an array of size n to store all net_exchange amount or X-Y
long long int amount[n+1];

// I'll initialize it to 0
fill(amount,amount+n+1,0);

// If X-Y becomes negetive then the guy has to give only, else he'll take only
for(int i=0 ; i < m ; i++){

long long int u,v,d; cin >> u >> v >> d;

amount[u] -= d;
amount[v] += d;

}

// We'll store all givers and takers like this , in a pair of integer.
vector < pair< long long int , long long int > > giver, taker;

// Here we are seperating givers from takers with their amounts.
for(int i = 1; i <= n ; i++){

if(amount[i] < 0){

// If amount is negetive, he's a giver
giver.push_back({i,-amount[i]});

}else if(amount[i] > 0){

// If amount is positive, he's a taker
taker.push_back({i,amount[i]});

}
}

// Now i'm sorting the givers and takers by their maximum amount.
sort(giver.begin(),giver.end(),mycomp);
sort(taker.begin(),taker.end(),mycomp);

// I'll use two pointers to simulate the process of transaction.
// 'i' for givers, and 'j' for takers.
int i = 0 , j = 0;

// This vector will store the transaction.
vector < pair< long long int, pair<long long int,long long int> > > res;

// So this while loop will untill there is at least one person in any line givers/takers.

while(i < giver.size()  &&  j < taker.size()){

// Here are the Person 1, Person 2, amount_1 and amount_2 in consideration.
long long int amount_1 = giver[i].second;
long long int person_1 = giver[i].first;
long long int amount_2 = taker[j].second;
long long int person_2 = taker[j].first;

if(amount_1 == amount_2){
// This is our first case, when amount_1 is equal to amount_2
res.push_back( { person_1 , { person_2 , amount_2 } } );

// We increment both pointers, to move to next persons in line.
i++;
j++;
}else if(amount_1 < amount_2){

// This is our first case, when amount_1 is less than to amount_2
res.push_back( { person_1 , { person_2 , amount_1 } } );

// We increment 'i' pointers, to move to next giver in line.
i++;

// And taker has taken some money from the giver but he's still left to take more
// so we subtract the amount he took right now
taker[j].second-=amount_1;

}else{

// This is our first case, when amount_1 is greater than to amount_2
res.push_back( { person_1 , { person_2 , amount_2 } } );

// We increment 'j' pointers, to move to next taker in line.
j++;

// And giver has given some money to the taker but he's still left to give more
// so we subtract the amount he gave right now
giver[i].second-=amount_2;
}
}

// We now output all transactions made.
cout << res.size() << endl;

for(auto x:res){
cout << x.first << ' ' << x.second.first << ' ' << x.second.second << endl;
}

return 0;
}
``````

I’m sorting the vectors of givers and takers, but i noticed that my solution gets accepted even if i don’t sort them.

I think it is a necessary condition to sort the vectors or is it? or the tests weak?

Also i saw this problem with a graph tag. Can someone tell me the graph based approach of this?

There’s no need to sort the vectors. We just need to minimize the sum of ‘debts’ and not the number of edges. It can be easily shown that minimum sum of debt no matter how you make matching from giver to taker.

That’s my question, how do you show it?

There are only outgoing edges from giver and incoming edges to taker.
Sum of debts is equal total weight of the edges. Weight of edges outgoing from a vertex (or incoming to a vertex) is always same not matter how you distribute it.

see my solution for reference.
https://codeforces.com/contest/1266/submission/67141908

Well now i understood the reason properly and can tell you why

The reason is that sum of all receivers amt is same as sum of all givers amt
No matter what pairs of transactions you make that is no matter what the distribution of money you give from a person to other it will not matter .

Lets take an example to clearly understand

Givers-> those who have to pay money

Case 1
Receivers amt is in increasing order and givers amt is in decreasing order
What will happen in this case is that initially each giver is able to pay many receivers that is 1 is able to pay 3-4 ( figures just for example)then second is able to pay next 3-4 and son on it will go on decreasing as the last set of givers will have to combine their money to pay the last receivers as they have lesser amounts of money and have to pay a large sum collectively.

Case 2
Receivers amt is in decreasing order and givers amt is in increasing order
A lot of givers will have to combine money to pay the first receiver as they have small amounts and first receiver has a huge amount of money to receive this will go on like this for initially.
Then towards the end receivers amt has decreased and givers amt has increased
so now a giver can pay 3-4 receivers and son on till the end.

Hence again the total number of transaction remains the same.

Case 3
Receivers amt is in increasing order and givers amt is in increasing order
This is what u have considered and every giver will try to pay the corresponding receiver to the best of his amt.
3 cases arise
1.If he is able to do so and no money is left we go to next giver and receiver .
2.If he is able to do so and has money is left we go to next receiver and he tries his best again .
3. If he is unable to pay a receiver he pays whatever he can and asks money from next giver .

Even in these case number of transaction will be the same as in above 2 cases.
this is essentially because of the fact that total money to be given is same as the total money to be received .

Case 4
Receivers amt is in decreasing order and givers amt is in decreasing order
This is opposite of what u have considered and every giver will try to pay the corresponding receiver to the best of his amt.
3 cases arise which arise are still same
1.If he is able to do so and no money is left we go to next giver and receiver .
2.If he is able to do so and has money is left we go to next receiver and he tries his best again .
3. If he is unable to pay a receiver he pays whatever he can and asks money from next giver .

Even in these case number of transaction will be the same as in above 2 cases.
this is essentially because of the fact that total money to be given is same as the total money to be received .

Case 5
Receivers amt and givers amt is both unsorted
Now this is what interests us all.

Now if you see and use the same 3 cases it will work perfectly fine.
This is because each giver will again try to do the same thing that is every giver will try to pay the corresponding receiver to the best of his amt.

3 cases arise which arise are still same
1.If he is able to do so and no money is left we go to next giver and receiver .
2.If he is able to do so and has money is left we go to next receiver and he tries his best again .
3. If he is unable to pay a receiver he pays whatever he can and asks money from next giver .

Now the number of transactions will still remain the same because no matter if we have a large giver in between then he will pay a large number of receivers which is compensated by a large receiver taking money from a large number of small receivers.
This compensation will be equal and opposite to each other and not affect the final result because of the fact that sum total of all money to be received is equal to the sum total of all money to be given.

Hope this explanation helps.

2 Likes

Thanks a lot I got it now