11659 - Informants

tryit1 · Post by **tryit1** » Mon Sep 07, 2009 10:14 am

how to solve this problem ?

Can you post links to similar problems.

Igor9669 · Post by **Igor9669** » Mon Sep 07, 2009 2:49 pm

I think that this test could help to find a solution for that problem, it is really easy.

20 0
0 0

answer is 20!

tryit1 · Post by **tryit1** » Mon Sep 07, 2009 4:01 pm

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 ?

Igor9669 · Post by **Igor9669** » Mon Sep 07, 2009 4:09 pm

You make it very hard yourself!
It is simple adhoc problem.
You need only one array and one loop! array=0 if informant "i" is not reliable and 1 if reliable. At first all array is 1!
Hope it helps!

tryit1 · Post by **tryit1** » Mon Sep 07, 2009 4:15 pm

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 ?

ecarrion · Post by **ecarrion** » Tue Sep 08, 2009 5:31 pm

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.

ecarrion · Post by **ecarrion** » Tue Sep 08, 2009 5:55 pm

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.

saiful_sust · Post by **saiful_sust** » Tue Sep 08, 2009 6:42 pm

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;
}

hasan3050 · Post by **hasan3050** » Wed Sep 09, 2009 3:20 am

try this input

Code: Select all

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

saiful_sust · Post by **saiful_sust** » Wed Sep 09, 2009 7:18 am

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;
}

Igor9669 · Post by **Igor9669** » Wed Sep 09, 2009 8:06 am

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

Answer should be 1!

Chimed · Post by **Chimed** » Wed Sep 09, 2009 8:21 am

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.

apurba · Post by **apurba** » Wed Sep 09, 2009 3:14 pm

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
Answer should be 1!

how could the answer be 1 !!!!!

Jehad Uddin · Post by **Jehad Uddin** » Wed Sep 09, 2009 4:45 pm

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,

ecarrion · Post by **ecarrion** » Thu Sep 10, 2009 12:55 am

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?

OJ Board