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

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

Re: 11659 - Informants

Post by Chimed » Thu Sep 10, 2009 6:08 am

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

hasan3050
New poster
Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

Re: 11659 - Informants

Post by hasan3050 » Fri Sep 11, 2009 2:12 am

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...... :wink: i think this will help u to get AC for this prob...... :D :) :P

apurba
New poster
Posts: 42
Joined: Sun Oct 07, 2007 10:29 pm

Re: 11659 - Informants

Post by apurba » Sat Sep 12, 2009 7:56 am

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...... :wink: i think this will help u to get AC for this prob...... :D :) :P
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...

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11659 - Informants

Post by peterkwan » Wed Oct 07, 2009 11:52 am

How about the following case:

Code: Select all

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

hasan3050
New poster
Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

Re: 11659 - Informants

Post by hasan3050 » Sat Oct 10, 2009 12:24 pm

the ans will be 1 :wink:

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11659 - Informants

Post by peterkwan » Sun Oct 11, 2009 8:06 am

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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11659 - Informants

Post by helloneo » Mon Oct 12, 2009 5:24 pm

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.
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
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11659 - Informants

Post by peterkwan » Tue Oct 13, 2009 7:43 am

hasan3050 wrote: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:
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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11659 - Informants

Post by helloneo » Tue Oct 13, 2009 3:58 pm

peterkwan wrote:
hasan3050 wrote: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:
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
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11659 - Informants

Post by peterkwan » Wed Oct 14, 2009 6:20 am

helloneo wrote: 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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 11659 - Informants

Post by helloneo » Wed Oct 14, 2009 2:30 pm

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

hasan3050
New poster
Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

Re: 11659 - Informants

Post by hasan3050 » Thu Oct 15, 2009 11:18 pm

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 :D
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 :D)....hope this will help u ....:D
Last edited by hasan3050 on Fri Oct 16, 2009 12:24 pm, edited 1 time in total.

peterkwan
New poster
Posts: 16
Joined: Sun Oct 28, 2007 1:54 pm

Re: 11659 - Informants

Post by peterkwan » Fri Oct 16, 2009 5:01 am

Please read carefully what I said :wink: :
If 1 is reliable, then
a)7 is not reliable, (since 7 says 1 is not reliable)
but you said:
hasan3050 wrote: 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". :wink:

Also,
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 :D)....hope this will help u ....:D
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
New poster
Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

Re: 11659 - Informants

Post by hasan3050 » Fri Oct 16, 2009 12:26 pm

it shows 1......

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

hasan3050
New poster
Posts: 8
Joined: Wed Sep 09, 2009 2:46 am

Re: 11659 - Informants

Post by hasan3050 » Fri Oct 16, 2009 12:34 pm

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

Post Reply

Return to “Volume 116 (11600-11699)”