11659 - Informants

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

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

11659 - Informants

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

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.

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

Re: 11659

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.

Code: Select all

20 0
0 0
answer is 20!

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11659

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 ?
Last edited by tryit1 on Mon Sep 07, 2009 4:10 pm, edited 1 time in total.

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

Re: 11659

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!

User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

Re: 11659

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
New poster
Posts: 3
Joined: Sun May 11, 2008 5:48 pm

Re: 11659

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

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
Learning poster
Posts: 97
Joined: Fri Aug 22, 2008 10:18 pm
Location: CSE.SUST.SYLHET

11659 - Informants

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

Ithink it is a easy problem

But I got WA........ :oops: :oops:

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
New poster
Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

Re: 11659 - Informants

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

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

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

Re: 11659 - Informants

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
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11659

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

3 2
1 -3
3 -2
0 0
Answer should be 1!

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

Re: 11659

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
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

Re: 11659

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 !!!!!

Code: Select all

keep dreaming...

Jehad Uddin
Learning poster
Posts: 74
Joined: Fri May 08, 2009 5:16 pm

Re: 11659 - Informants

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, :D :lol: 8)

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

Re: 11659 - Informants

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, :D :lol: 8)
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?

Post Reply

Return to “Volume 116 (11600-11699)”