538 - Balancing Bank Accounts

All about problems in Volume 5. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

538 - balancing bank acounts (please help)

Post by ei01036 » Wed Jan 15, 2003 1:20 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

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

538 - Balancing Bank Accounts

Post by Maxim » Mon May 12, 2003 12:26 pm

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

Post by miras » Fri Jun 11, 2004 11:37 am

try to do it using Greedy... ;-)
Remember Never Give Up
Regrads
Miras

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Fri Jun 11, 2004 11:38 am

No No ii solvbed it using Greedy...
Remember Never Give Up
Regrads
Miras

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

538 please help

Post by oulongbin » Mon Jan 31, 2005 10:17 am

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


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

some test cases

Post by Sedefcho » Tue Feb 08, 2005 8:59 pm

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


Please note the following:
(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.)"

I hope these test cases will help you.

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

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

small correction of a typo

Post by Sedefcho » Tue Feb 08, 2005 9:01 pm

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.)".

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

Several ( Important , I hope ) Notes

Post by Sedefcho » Tue Feb 08, 2005 9:11 pm

(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,
output ``B A 20" instead.


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.

Post by WR » Wed Mar 02, 2005 9:13 am

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.

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

Post by Sedefcho » Wed Mar 02, 2005 1:14 pm

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

Post by hasib_bd » Sat May 31, 2008 8:13 pm

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

Re: 538 please help

Post by hasib_bd » Sat May 31, 2008 8:26 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:

reply3

Post by ipodfansmail » Thu Jul 31, 2008 12:05 pm

Wow! This post rocks

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

Re: 538 - Balancing Bank Accounts

Post by mice123456789 » Tue Sep 08, 2009 7:50 pm

Someone, please validate my output. Keep WA :(
Thanks in advance.

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
Location: Bangladesh
Contact:

Re: 538 - Balancing Bank Accounts

Post by Imti » Sun Jan 30, 2011 11:18 am

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

Post Reply

Return to “Volume 5 (500-599)”