## 11690 - Money Matters

Moderator: Board moderators

durjay
New poster
Posts: 13
Joined: Tue Oct 06, 2009 5:09 pm
Location: ctg

### 11690

I solve the this problem by DFS. but it is time limit exceed. here is my code:

#include<stdio.h>

long int k1;

long int g[10001][10001]={0},cl[10001];

long int d,cu[10001];

int dfs();

void dfs_visit(int u);

int main()

{

long int u,r,j,a,y;

long int c,s,i,t;

scanf("%ld",&t);

for(i=1;i<=t;i++)

{

scanf("%ld%ld",&u,&r);

d=u;

for(j=0;j<u;j++)

scanf("%ld",&cu[j]);

for(j=0;j<r;j++)

{

scanf("%ld%ld",&a,&y);

g[a][y]=1;

g[y][a]=1;

}

r=dfs();

if(r==0)

printf("IMPOSSIBLE\n");

else

printf("POSSIBLE\n");

for(c=0;c<d;c++)

for(s=0;s<d;s++)

g[c][s]=0;

}

return 0;

}

int dfs()

{

int i;

for(i=0;i<d;i++)

{

cl=1;

}

for(i=0;i<d;i++)

{

if(cl==1)

{

k1=0;

k1=k1+cu;

dfs_visit(i);

if(k1<0)

{

return 0;

break;

}

}

}

return 1;

}

void dfs_visit(int u)

{

int i;

cl=2;

for(i=0;i<d;i++)

{

if(g==1)

{

if(cl==1)

{

k1=k1+cu;

dfs_visit(i);

}

}

}

cl=3;

}

plz help me.

durjay
New poster
Posts: 13
Joined: Tue Oct 06, 2009 5:09 pm
Location: ctg

### 11690 - Money Matters

accepted
Last edited by durjay on Sat Dec 19, 2009 9:17 pm, edited 1 time in total.

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

### Re: 11690 MONEY MATTERS

You use a lot of memory(about 400 MB), your solution wouldn't work!

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11690 MONEY MATTERS

Hi durjay...
Try to solve it with set operation ..............
it is a easy problem..............
Always think easy.........

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 11690 MONEY MATTERS

Durjoy
Try to use Vector
i got it accepted using vector
Try to catch fish rather than asking for some fishes.

saiful_sust
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

### Re: 11690 MONEY MATTERS

Durjoy
try it with set operation

u have to find disjoin set and total sum of every set = 0 than it is possible
else impossible

EX: if 1 and 2 is friend, 3 and 4 is friend than there is two set.

but when 2 and 3 is friend than there is 1 set that is {1,2,3};

I think that is enough.............
try it .....
Last edited by saiful_sust on Thu Oct 15, 2009 12:12 pm, edited 1 time in total.

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 11690 MONEY MATTERS

Durjoy
remove ur code if u got accepted
Try to catch fish rather than asking for some fishes.

poixp
New poster
Posts: 20
Joined: Mon Apr 07, 2008 11:05 am

### Re: 11690 MONEY MATTERS

The solution with matrix also works if you chose the correct data type. Long int is overhead.

Taman
New poster
Posts: 32
Joined: Sun Oct 11, 2009 8:59 pm
Location: Southeast University

### Re: 11690 MONEY MATTERS

Thanks to Arifcsecu. . .ur reply to Durjay helped me a lot. . .

arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

### Re: 11690 MONEY MATTERS

Taman wrote:Thanks to Arifcsecu. . .ur reply to Durjay helped me a lot. . .
It is OK
Try to catch fish rather than asking for some fishes.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11690 MONEY MATTERS

Input:

Code: Select all

``````1
5 4
1
1
1
1
-4
0 1
2 3
1 2
3 4``````
AC output POSSIBLE
Check input and AC output for thousands of problems on uDebug!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 11690 MONEY MATTERS

Accepted.
Last edited by moxlotus on Wed Sep 11, 2013 11:05 am, edited 2 times in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11690 MONEY MATTERS

Use class Main
Check input and AC output for thousands of problems on uDebug!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

### Re: 11690 MONEY MATTERS

My submitted code is using Main. still it didnt work. =(
Do u have any other test cases to help me out ? Thanks
brianfry713 wrote:Use class Main

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 11690 MONEY MATTERS

Remove line 72:
count --;
Check input and AC output for thousands of problems on uDebug!