11659 - Informants

[Chimed]

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?

Yes answer is 2.

[hasan3050]

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

[apurba]

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

[peterkwan]

How about the following case:

Code: Select all

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

[hasan3050]

the ans will be 1

[peterkwan]

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

[helloneo]

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

Try this case..

Code: Select all

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

My output is..

Code: Select all

3

[peterkwan]

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

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

[helloneo]

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

I 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)

..

On that case, 2 can be also reliable..

[peterkwan]

On that case, 2 can be also reliable..

Yes, 2 can be reliable. Please tell me whether my following logic to solve the problem is incorrect:

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.

[helloneo]

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

[hasan3050]

for this input......

Code: Select all

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

my ac code shows 18

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

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 says

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

.....from my thinking... 7 and 4 are 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 ....

[peterkwan]

Please read carefully what I said :

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

but you said:

i think there's a little prob with ur thinking.......in ur thinking......if 1 is not reliable then 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.....

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

Also,

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

What is the output of your accepted code for the following case?

Code: Select all

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

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

[hasan3050]

it shows 1......

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

[hasan3050]

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