## 538 - Balancing Bank Accounts

Moderator: Board moderators

ei01036
New poster
Posts: 12
Joined: Wed Jan 15, 2003 1:13 am

i'm trying to solve 538, and my program solves (aparently) all the possible cases... is there any "weird" case or some tip i'm missing?

tanx

Maxim
New poster
Posts: 38
Joined: Tue Aug 27, 2002 12:36 am
Location: Croatia
Contact:

### 538 - Balancing Bank Accounts

Can anyone tell me or prove whether this problem can be solved using Network flow?

Thanks,
Maxim

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
try to do it using Greedy...
Remember Never Give Up
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm
No No ii solvbed it using Greedy...
Remember Never Give Up
Miras

oulongbin
Learning poster
Posts: 53
Joined: Sat Jul 10, 2004 5:57 pm
Location: Shanghai China

i don't know why i got WA.
could somebody give me sum special cases,thank you very much!

Code: Select all

#include <iostream>
using namespace std;
#include <cstring>

typedef struct
{
char name1[100];
char name2[100];
int mon;
}output;

int main()
{
output out[50];
int o;
int n,t;
char name[50][100];
char cname[50][100];
char n1[100],n2[100];
char cn[100];
int money[50];
int x,y;
int cas=1;
int m;
int i,j,k;
while(cin>>n>>t)
{
if(n==0&&t==0)
break;
for(i=1;i<=n;i++)
{
cin>>name[i];
strcpy(cname[i],name[i]);
money[i]=0;
}
for(i=0;i<t;i++)
{
cin>>n1>>n2>>m;
x=y=-1;
for(j=1;j<=n;j++)
{
if(!strcmp(n1,name[j]))
{
x=j;
}
if(!strcmp(n2,name[j]))
{
y=j;
}
if(x!=-1&&y!=-1)
break;
}
if(x!=-1&&y!=-1)
{
money[x]-=m;
money[y]+=m;
}
}
for(i=1;i<=n-1;i++)
{
for(j=1;j<=n-i-1;j++)
{
if(money[j]>money[j+1])
{
m=money[j];
money[j]=money[j+1];
money[j+1]=m;
strcpy(cn,name[j]);
strcpy(name[j],name[j+1]);
strcpy(name[j+1],cn);
}
}
}

i=1;j=n;o=1;
cout<<"Case #"<<cas++<<endl;
while(i<j)
{
for(k=1;k<=n;k++)
{
if(money[k]!=0)
break;
}
if(k==n+1)
break;
if(money[i]<0)
{
if(money[i]+money[j]<0)
{
money[i]+=money[j];
strcpy(out[o].name1,name[j]);
strcpy(out[o].name2,name[i]);
out[o++].mon=money[j];
money[j]=0;
j--;
}
else if(money[i]+money[j]>0)
{
money[j]+=money[i];
strcpy(out[o].name1,name[j]);
strcpy(out[o].name2,name[i]);
out[o++].mon=-money[i];
money[i]=0;
i++;
}
else
{
strcpy(out[o].name1,name[j]);
strcpy(out[o].name2,name[i]);
out[o++].mon=money[j];
money[i]=money[j]=0;
i++;
j--;
}
}
else
{
i++;
}

}

for(j=1;j<=n;j++)
{
k=1;
while(k<o)
{
if(!strcmp(cname[j],out[k].name1))
{
cout<<out[k].name1<<" "<<out[k].name2<<" "<<out[k].mon<<endl;
}
k++;
}
}
cout<<endl;
}
return 0;
}

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### some test cases

Here are some test inputs ( I hope they are useful to you ).

Code: Select all

=======
INPUT:
=======
2 1
Donald
Dagobert
Donald Dagobert 15
4 4
John
Mary
Cindy
Arnold
John Mary 100
John Cindy 200
Cindy Mary 40
Cindy Arnold 150
2 1
Donald
Dagobert
Donald Dagobert 15
2 4
Donald
Dagobert
Donald Dagobert 15
Dagobert Donald  15
Dagobert Donald  5
Donald Dagobert 5
2 1
Donald
Dagobert
Donald Dagobert 15
0 0

Code: Select all

=======
OUTPUT:
=======
Case #1
Dagobert Donald 15

Case #2
Arnold John 150
Mary John 140
Cindy John 10

Case #3
Dagobert Donald 15

Case #4

Case #5
Dagobert Donald 15

(1) My program gets "Accepted P.E." and not a clear "Accepted"
(2) The reason for (1) is not the output of two empty lines
for cases like my Case#4. I haven't tried printing just one empty
line in cases when noone should give money to noone.
Even with this change I still get "Accepted (P.E.)"

Peter Petrov
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:19741

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### small correction of a typo

C O R R E C T I O N:

(2) The reason for (1) is not the output of two empty lines
for cases like my Case#4.
I HAVE TRIED printing just one empty
line in cases when noone should give money to noone.
Even with this change I still get "Accepted (P.E.)".

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria

### Several ( Important , I hope ) Notes

(3) Important note:
They say that in case when the solutions are
more than one you can print any of it.
Suppose the minimal count of transactions you need in order
to balance the accounts is S and let's suppose S <= N-3.
Here N is the count of the people.

If you print a solution including S+1 transactions it will still be
OK ( theoretically ) as they only pose these requirements:

- Your solution must consist of at most N-1 transactions
- Amounts may not be negative, i.e. never output A B -20,

But I am not sure they will recognize your solution if you have
a transaction count bigger than S ( S is the minimal possible
transaction count allowing you to balance the accounts ).

(4) One more important note:
Seems they have test cases where
N ( the count of people ) is > 20.
Which violates their promise for N<=20.

I have a value of 30 in
my program for my constant MAX_PEOPLE.
With MAX_PEOPLE=20 the Judge was giving me : Wrong Answer.

Peter Petrov
http://acm.uva.es/cgi-bin/OnlineJudge?AuthorInfo:19741

WR
Experienced poster
Posts: 145
Joined: Thu Nov 27, 2003 9:46 am

### p.e.

sedefcho,

could it be that you forgot to print a blank line even after the last case?

For your sample my output is the same as yours apart from that last line and my program has been accepted without a p.e.

Sedefcho
A great helper
Posts: 374
Joined: Sun Jan 16, 2005 10:18 pm
Location: Bulgaria
Anyway, I am not going to investigate that any further.

I am not a real contester, so anyway ...

hasib_bd
New poster
Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

### Re: 538 - Balancing Bank Accounts

Yes,
Greedy seems enough to comply with "Your solution must consist of at most n-1 transactions."
I also got AC with greedy to compute the transactions.

hasib_bd
New poster
Posts: 14
Joined: Wed Apr 30, 2008 12:39 pm

following input/output may help (generated by my AC program using greedy algo):
Input

Code: Select all

2 1
Donald
Dagobert
Donald Dagobert 15
4 4
John
Mary
Cindy
Arnold
John Mary 100
John Cindy 200
Cindy Mary 40
Cindy Arnold 150
2 2
A
B
A B 10
B A 10
5 6
A
B
C
D
E
A B 50
B C 10
D E 20
E A 5
A D 20
D B 15
0 0
Output:

Code: Select all

Case #1
Dagobert Donald 15

Case #2
Arnold John 150
Mary John 140
Cindy John 10

Case #3

Case #4
B A 55
E A 10
E D 5
C D 10

I also got AC while my program generated output like below:

Code: Select all

Case #1
Dagobert Donald 15

Case #2
Arnold John 150
Mary John 140
Cindy John 10

Case #3
Case #4
B A 55
E A 10
E D 5
C D 10

ipodfansmail
New poster
Posts: 1
Joined: Thu Jul 31, 2008 4:03 am
Contact:

Wow! This post rocks

mice123456789
New poster
Posts: 12
Joined: Tue Aug 27, 2002 6:09 pm

### Re: 538 - Balancing Bank Accounts

Someone, please validate my output. Keep WA

Code: Select all

Case #1
Dagobert Donald 15

Case #2
Cindy John 10
Mary John 140
Arnold John 150

Case #3

Case #4
C A 10
E A 15
B A 40
B D 15

Imti
Learning poster
Posts: 53
Joined: Sat Dec 04, 2010 12:00 pm
Contact:

### Re: 538 - Balancing Bank Accounts

Dear hasib_bd my program outputs following for your sample input.Please verify it anyone?

Code: Select all

2 1
Donald
Dagobert
Donald Dagobert 15
Case #1
Dagobert Donald 15

4 4
John
Mary
Cindy
Arnold
John Mary 100
John Cindy 200
Cindy Mary 40
Cindy Arnold 150
Case #2
Arnold John 150
Cindy John 10
Mary John 140

2 2
A
B
A B 10
B A 10
Case #3

5 6
A
B
C
D
E
A B 50
B C 10
D E 20
E A 5
A D 20
D B 15
Case #4
B A 55
C A 10
E D 15

0 0
Press any key to continue