Yes answer is 2.ecarrion wrote: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?

## 11659 - Informants

**Moderator:** Board moderators

### Re: 11659 - Informants

### Re: 11659 - Informants

this prob is really very easy......it says to find out MAXIMUM no of reliable ans......so if any one says that "A" is not reliable......then we don't need to bother about "A"......even if next time anyone says that "A" is reliable......bcz A is already out of focus...... i think this will help u to get AC for this prob......

### Re: 11659 - Informants

hasan3050 wrote:this prob is really very easy......it says to find out MAXIMUM no of reliable ans......so if any one says that "A" is not reliable......then we don't need to bother about "A"......even if next time anyone says that "A" is reliable......bcz A is already out of focus...... i think this will help u to get AC for this prob......

**But i can't understand what if someone not reliable and say something, then should we ignore it or make it count???**

Code: Select all

`keep dreaming...`

### Re: 11659 - Informants

How about the following case:

Code: Select all

```
5 5
1 -2
2 -1
4 -1
3 -4
5 -3
```

### Re: 11659 - Informants

the ans will be 1

### Re: 11659 - Informants

My code passed the test cases as listed in this thread, but I still get WA. What is wrong with my code? Thanks.

Code: Select all

```
#include <iostream>
using namespace std;
main() {
int i, a, x, y;
while (cin >> i >> a) {
if (i==0 && a==0) break;
bool b[i];
for (int j=0; j<i; j++)
b[j]=true;
for (int j=0; j<a; j++) {
cin >> x >> y;
if (b[x-1]) {
if (y<0)
b[-1*y-1]=false;
}
/*for (int k=0; k<i; k++) {
cout << "B[K]=" << b[k] << " ";
}
cout << endl;*/
}
int c = 0;
for (int j=0; j<i; j++) {
if (b[j]) c++;
}
cout << c << endl;
}
return 0;
}
```

### Re: 11659 - Informants

Try this case..peterkwan wrote:My code passed the test cases as listed in this thread, but I still get WA. What is wrong with my code? Thanks.

Code: Select all

```
4 5
1 -2
1 -3
1 -4
2 3
2 4
0 0
```

Code: Select all

`3`

### Re: 11659 - Informants

I don't quite understand why this input causes 18. From my understanding,hasan3050 wrote:try this inputthe 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`

If 1 is reliable, then

a) 7 is not reliable, (since 7 says 1 is not reliable) and

b) 3 is not reliable. (since 1 says 3 is not reliable) => 4 is also not reliable as well (since 4 says 3 is reliable)

In this case, the output is 17 (since 3, 4, 7 are not reliable).

If 1 is not reliable, then

a) 3 is not reliable (since 3 says 1 is reliable) => 4 is not reliable (since 4 says 3 is reliable)

In this case, the output is also 17 (since 1, 3, 4 are not reliable).

Please help what is wrong with the above logic.

### Re: 11659 - Informants

On that case, 2 can be also reliable..peterkwan wrote:I don't quite understand why this input causes 18. From my understanding,hasan3050 wrote:try this inputthe 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`

If 1 is reliable, then

a) 7 is not reliable, (since 7 says 1 is not reliable) and

b) 3 is not reliable. (since 1 says 3 is not reliable) => 4 is also not reliable as well (since 4 says 3 is reliable)

..

### Re: 11659 - Informants

Yes, 2 can be reliable. Please tell me whether my following logic to solve the problem is incorrect:helloneo wrote: On that case, 2 can be also reliable..

for each input of X and Y,

(

BX = The current state of X

BY = The current state of Y

If BX is not set and BY is not set

=> set BX = 1 or 0

If BX is set but BY is not set

{

BX = 1 and Y > 0 => BY = 1

BX = 1 and Y < 0 => BY = 0

BX = 0 => BY = 1 or 0

}

else If BX not is set but BY is set

{

BY = 1 and Y > 0 => BX = 1 or 0

BY = 0 and Y > 0 => BX = 0

BY = 1 and Y < 0 => BX = 0

BY = 0 and Y < 0 => BX = 1 or 0

}

else If BX is set and BY is set

{

BX = 1 and Y > 0 and BY = 1 => OK

BX = 1 and Y < 0 and BY = 0 => OK

BX = 0 and BY = 1 or 0 => OK

Otherwise, not OK => prune this solution

}

)

If any BX is not set after parsing all input, set BX = 1

=> Finally check the number of 1 set, and output the max one.

If I applied the above logic to the sample input, we get:

First case: B1 = 1

1 -3 => 1_0 (underscore represents the BX is not set)

2 -3 => 110 or 100

3 1 => 110 or 100

2 2 => 110 or 100

7 -1 =>110___0 or 100___0

4 3 => 1100__0 or 1000__0

Max is:

-> 1100110 .... (13 1's)

-> So this case, number of 1's is 17

Second case: B1 = 0

1 -3 => 0_0 or 0_1

2 -3 => 010 or 000 or 001

3 1 => check contradiction => 010 or 000 (001 is contradict with 1 -3)

2 2 => 010 or 000

7 -1 => 010___1 or 010___0 or 000___1 or 000___0

4 3 => 0100__1 or 0100__0 or 0000__1 or 0000__0

Max is:

-> 0100111 ... (13 1's)

-> So this case, number of 1's is also 17.

How can the maximum number of informants be 18? Thanks.

### Re: 11659 - Informants

peterkwan wrote: ...

...

If I applied the above logic to the sample input, we get:

First case: B1 = 1

1 -3 => 1_0 (underscore represents the BX is not set)

2 -3 => 110 or 100

3 1 => 110 or 100

2 2 => 110 or 100

7 -1 =>110___0 or 100___0

4 3 => 1100__0 or 1000__0

Max is:

-> 1100110 .... (13 1's)

-> So this case, number of 1's is 17

Second case: B1 = 0

1 -3 => 0_0 or 0_1

2 -3 => 010 or 000 or 001

3 1 => check contradiction => 010 or 000 (001 is contradict with 1 -3)

2 2 => 010 or 000

7 -1 => 010___1 or 010___0 or 000___1 or 000___0

4 3 => 0100__1 or 0100__0 or 0000__1 or 0000__0

Max is:

-> 0100111 ... (13 1's)

-> So this case, number of 1's is also 17.

How can the maximum number of informants be 18? Thanks.

You're right..

My AC code also prints 17

By the way, I think you should try Bx = 1 or Bx = 0 for each x (1 <= x <= n) instead of trying only B1

### Re: 11659 - Informants

for this input......
my ac code shows 18

any way my logic to solve this prob was: at first i assumed that all are reliable(for this case number of reliable,R=20)....then if i get any one not reliable then decrease R by one(in this case 3 and 1 are not reliable.....so decrease it by 2).....and print the ans(and thats why the ans is 18 )....hope this will help u ....

Code: Select all

```
20 6
1 -3
2 -3
3 1
2 2
7 -1
4 3
```

i think there's a little prob with ur thinking.......in ur thinking......if 1 is reliable then 7 is not reliable(as it says 1 is not reliable).......but i think thats not right as the prob saysI don't quite understand why this input causes 18. From my understanding,

If 1 is reliable, then

a) 7 is not reliable, (since 7 says 1 is not reliable) and

b) 3 is not reliable. (since 1 says 3 is not reliable) => 4 is also not reliable as well (since 4 says 3 is reliable)

In this case, the output is 17 (since 3, 4, 7 are not reliable).

If 1 is not reliable, then

a) 3 is not reliable (since 3 says 1 is reliable) => 4 is not reliable (since 4 says 3 is reliable)

In this case, the output is also 17 (since 1, 3, 4 are not reliable).

Please help what is wrong with the above logic.

.....from my thinking... 7 and 4 areIf X happens to be reliable, the ACM assumes that whatever he

or she says, can be interpreted to be true. Otherwise, if X is not reliable, his or her opinions may be either true or false.

**reliable**as no one says that**they are not reliable**....any way my logic to solve this prob was: at first i assumed that all are reliable(for this case number of reliable,R=20)....then if i get any one not reliable then decrease R by one(in this case 3 and 1 are not reliable.....so decrease it by 2).....and print the ans(and thats why the ans is 18 )....hope this will help u ....

Last edited by hasan3050 on Fri Oct 16, 2009 12:24 pm, edited 1 time in total.

### Re: 11659 - Informants

Please read carefully what I said :

Also,
My code will output 3 (i.e. 2, 3, 4 are reliable).

but you said:If 1 is reliable, then

a)7 is not reliable, (since 7 says 1 is not reliable)

I don't think 7 could be reliable. If 7 is reliable and he says 1 is not reliable, then 1 is not reliable, which contradicts "If 1 is reliable".hasan3050 wrote: i think there's a little prob with ur thinking.......in ur thinking......if 1 is not reliablethen 7 is obviously not reliable.......but i think thats not right as the prob says

so 7 may be reliable or may be not.....and as u have to find out the maximum no of reliables....i think u hav to consider 7 as a reliable one.....

Also,

What is the output of your accepted code for the following case?hasan3050 wrote: any way my logic to solve this prob was: at first i assumed that all are reliable(for this case number of reliable,R=20)....then if i get any one not reliable then decrease R by one(in this case 3 and 1 are not reliable.....so decrease it by 2).....and print the ans(and thats why the ans is 18 )....hope this will help u ....

Code: Select all

```
4 5
1 -2
1 -3
1 -4
2 3
2 4
0 0
```

### Re: 11659 - Informants

it shows 1......

sry for the mistake ....i've edited that

sry for the mistake ....i've edited that

### Re: 11659 - Informants

my assumption for this ans is: there is no one said about 1.....so we have to consider that 1 is true.....and as he is true.....2,3,4 are false....

and if there was another statement like 2 -1....then the ans would be 0.......as 2 says that 1 is false...lets consider 1 is false.....as false can give a true ans too .....so 2,3,4 may be false too....and the maximum may be true is 0.....

and if there was another statement like 2 -1....then the ans would be 0.......as 2 says that 1 is false...lets consider 1 is false.....as false can give a true ans too .....so 2,3,4 may be false too....and the maximum may be true is 0.....