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 » Tue Oct 06, 2009 5:54 pm

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 » Tue Oct 06, 2009 6:02 pm

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 » Tue Oct 06, 2009 6:26 pm

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 » Tue Oct 06, 2009 8:37 pm

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 » Tue Oct 06, 2009 9:33 pm

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 » Wed Oct 07, 2009 6:09 pm

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 » Wed Oct 14, 2009 7:43 pm

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 » Thu Oct 22, 2009 7:18 am

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 » Thu Nov 12, 2009 10:28 pm

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 » Fri Nov 13, 2009 3:31 pm

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 » Wed Dec 05, 2012 9:49 am

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 » Fri Sep 06, 2013 2:43 pm

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 » Fri Sep 06, 2013 10:43 pm

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 » Sat Sep 07, 2013 4:24 pm

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 » Mon Sep 09, 2013 11:42 pm

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

Post Reply

Return to “Volume 116 (11600-11699)”