538 - Balancing Bank Accounts

[ei01036]

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]

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

Thanks,
Maxim

[miras]

try to do it using Greedy...

[miras]

No No ii solvbed it using Greedy...

[oulongbin]

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]

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

[Sedefcho]

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]

(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]

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]

Anyway, I am not going to investigate that any further.

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

[hasib_bd]

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]

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]

Wow! This post rocks

[mice123456789]

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]

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