11690 - Money Matters

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

Moderator: Board moderators

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

11690

Post by durjay »

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

Post by durjay »

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

Post by Igor9669 »

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

Post by saiful_sust »

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

Post by arifcsecu »

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

Post by saiful_sust »

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 ..... :D
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

Post by arifcsecu »

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

Post by poixp »

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

Post by Taman »

Thanks to Arifcsecu. . .ur reply to Durjay helped me a lot. . . :D
arifcsecu
Learning poster
Posts: 64
Joined: Fri Sep 25, 2009 11:29 am
Location: Chittagong,University of chittagong
Contact:

Re: 11690 MONEY MATTERS

Post by arifcsecu »

Taman wrote:Thanks to Arifcsecu. . .ur reply to Durjay helped me a lot. . . :D
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

Post by brianfry713 »

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

Post by moxlotus »

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

Post by brianfry713 »

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

Post by moxlotus »

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

Post by brianfry713 »

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

Return to “Volume 116 (11600-11699)”