11659 - Informants
Moderator: Board moderators
11659 - Informants
how to solve this problem ?
Can you post links to similar problems.
Can you post links to similar problems.
Last edited by tryit1 on Wed Sep 09, 2009 1:32 pm, edited 1 time in total.
Re: 11659
I think that this test could help to find a solution for that problem, it is really easy.
answer is 20!
Code: Select all
20 0
0 0
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 ?
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 ?
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.
Re: 11659
Can you tell me how we get 2 informans as reliable ? how would you approach the above example. Any similar problems ?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.
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.
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.
Re: 11659
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.tryit1 wrote:Can you tell me how we get 2 informans as reliable ? how would you approach the above example. Any similar problems ?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.
So A and B are the only one reliables, so the answer is 2.
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
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;
}
Re: 11659 - Informants
try this input
the rigth out put should be 18......your code shows 19.....
Code: Select all
20 6
1 -3
2 -3
3 1
2 2
7 -1
4 3
-
- Learning poster
- Posts: 97
- Joined: Fri Aug 22, 2008 10:18 pm
- Location: CSE.SUST.SYLHET
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;
}
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:
Answer should be 1!
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
Re: 11659
how could the answer be 1 !!!!!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:Answer should be 1!Code: Select all
3 2 1 -3 3 -2 0 0
Code: Select all
keep dreaming...
-
- Learning poster
- Posts: 74
- Joined: Fri May 08, 2009 5:16 pm
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,
Re: 11659 - Informants
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.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,
Did I misunderstood the problem statemen?