## 11659 - Informants

Moderator: Board moderators

### 11659 - Informants

how to solve this problem ?

Can you post links to similar problems.
Last edited by tryit1 on Wed Sep 09, 2009 1:32 pm, edited 1 time in total.

tryit1
Experienced poster

Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11659

I think that this test could help to find a solution for that problem, it is really easy.
Code: Select all
20 0
0 0

Igor9669
Learning poster

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

### Re: 11659

yes it is 20 because the mask 2^20 -1 is satisfied by all things. I don't understand how to formulate this problem and i find this problem VERY HARD. I really don't now how to solve this one. Can you give me more examples ,smaller ones so that i can relate it understand and use it to test my program.

Should we do something like this ?
dfs()
for each person ,
assume he is speaking truth,
-> All reliables are speaking truth
dfs(for each reliable)
if he is false
do nothing.

The problem is with conflicts, a future reliable can conflict with current not reliable and a current not reliable can be future reliable. This causes confusion. Maybe this is wrong approach. Can you tell me similar problems ?
Last edited by tryit1 on Mon Sep 07, 2009 4:10 pm, edited 1 time in total.

tryit1
Experienced poster

Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11659

You make it very hard yourself!
You need only one array and one loop! array[i]=0 if informant "i" is not reliable and 1 if reliable. At first all array is 1!
Hope it helps!
Igor9669
Learning poster

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

### Re: 11659

As an example, let's assume there are four informants A, B, C and D, with the following surveyed answers: ``A says B is reliable but D is not'', ``B says C is not reliable'', and ``C says A and D are reliable''. In this case, it happens that at most two informants are reliable.

Can you tell me how we get 2 informans as reliable ? how would you approach the above example. Any similar problems ?

tryit1
Experienced poster

Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### Re: 11659

Hi, how and imput like this should be treated.

6 4
1 2
2 -3
1 4
4 -2

Would the answer be 5 or 4?

I mean that if we have to look for all transitive relations? and if we have to, on some special cases, wouldn't it take us to an endless loop?

Thanks.
Last edited by ecarrion on Tue Sep 08, 2009 6:06 pm, edited 2 times in total.
ecarrion
New poster

Posts: 3
Joined: Sun May 11, 2008 5:48 pm

### Re: 11659

tryit1 wrote:
As an example, let's assume there are four informants A, B, C and D, with the following surveyed answers: ``A says B is reliable but D is not'', ``B says C is not reliable'', and ``C says A and D are reliable''. In this case, it happens that at most two informants are reliable.

Can you tell me how we get 2 informans as reliable ? how would you approach the above example. Any similar problems ?

It is simple, in ther first step all informants are reliable, then A says B is reliable bit D is not, so we got all informants reliable except D, then B wich is reliable says than C is not reliable, so we got A,B reliable and C,D not reliable, then C says that A and D are reliable, but since C is not reliable we should ignore what he or she is saying.

So A and B are the only one reliables, so the answer is 2.
ecarrion
New poster

Posts: 3
Joined: Sun May 11, 2008 5:48 pm

### 11659 - Informants

Ithink it is a easy problem

But I got WA........

Some one PLZ check my code.........

Code: Select all
#include<stdio.h>
#include<stdlib.h>

int a[803];

int main()
{
int i,n,b,c,m,Count,j,d;
while(scanf("%d%d",&m,&n)==2 && (m || n))
{
Count= 0;
for(i=1;i<=m;i++)
a[i]=1;
for(i=1;i<=n;i++)
{
scanf("%d%d",&b,&c);

if(a[b])
{
if( c > 0)
{
a[c] = 1;

}
else if(c < 0)
{
d = (-1)*c;
a[d] = 0;
}
}
}
for(i=1;i<=m;i++)
{
if(a[i])
Count++;
}
printf("%d\n",Count);
}
return 0;
}
saiful_sust
Learning poster

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

### Re: 11659 - Informants

try this input
Code: Select all
20 6
1 -3
2 -3
3 1
2 2
7 -1
4 3

the rigth out put should be 18......your code shows 19.....
hasan3050
New poster

Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

### Re: 11659 - Informants

Thanks hasan3050 for ur test case
I solve this test case But again WA
My modified code Here:
PLZ help me.....

Code: Select all
#include<stdio.h>
#include<stdlib.h>

int a[803];

int main()
{
int i,n,b,c,m,Count,d,e;
//freopen("a.txt","r",stdin);
while(scanf("%d%d",&m,&n)==2 && (m || n))
{
Count= 0;
for(i=1;i<=m;i++)
a[i]=1;
for(i=1;i<=n;i++)
{
scanf("%d%d",&b,&c);
e = c;
if( e < 0)
{
e = (-1)*e;
}
if( (a[b]==2) && ( a[e] > 0) )
{
if( c > 0)
{
a[c] = 2;

}
else if(c < 0)
{
a[e] = 0;
}
}
else if( (a[b]==1) && ( a[e] > 0) )
{
if( c > 0)
{
a[c] = 2;

}
else if(c < 0)
{
a[e] = 0;
}
}
}

for(i=1;i<=m;i++)
{
//printf("a [%d] == %d\n",i,a[i]);
if(a[i]>=1)
Count++;
}
printf("\n%d\n",Count);
}
return 0;
}
saiful_sust
Learning poster

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

### Re: 11659

First you print leading new line!
Second why do you use such a big array you need only 20 elements and third try this test:
Code: Select all
3 2
1 -3
3 -2
0 0

Igor9669
Learning poster

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

### Re: 11659

tryit1 wrote:how to solve this problem ?

Can you post links to similar problems.

"tryit1": can you put problem name when you creating new thread.
Chimed
New poster

Posts: 12
Joined: Mon Oct 20, 2008 10:37 am

### Re: 11659

Igor9669 wrote:First you print leading new line!
Second why do you use such a big array you need only 20 elements and third try this test:
Code: Select all
3 2
1 -3
3 -2
0 0

how could the answer be 1 !!!!!
Code: Select all
keep dreaming...
apurba
New poster

Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm
Location: In Front of Computer

### Re: 11659 - Informants

because 3 isnt reliable and 2 isnt reliable ,so only 1 is reliable so ans is 1,its so simple problem,try all the I/Os in the board,
Learning poster

Posts: 74
Joined: Fri May 08, 2009 5:16 pm

### Re: 11659 - Informants

Jehad Uddin wrote:because 3 isnt reliable and 2 isnt reliable ,so only 1 is reliable so ans is 1,its so simple problem,try all the I/Os in the board,

I think that the problem says that when an informant is not reliable, their words can be true or false, so I don't se a way of how 2 is not relieabe.
Did I misunderstood the problem statemen?
ecarrion
New poster

Posts: 3
Joined: Sun May 11, 2008 5:48 pm

Next