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
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11659 - Informants

Post by plamplam » Fri Sep 07, 2012 11:36 am

Some test cases:

Code: Select all

19 3
12 -10
16 -4
9 11

2 6
1 -1
2 2
2 -1
2 1
1 2
2 -1

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

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

11 5
11 8
6 8
4 -11
3 -1
9 1

11 1
5 -6

10 10
4 -2
1 4
6 -2
7 -5
9 -7
8 -2
10 4
9 -8
6 5
8 -4

6 9
3 -4
3 5
2 -2
1 2
1 3
4 -3
2 5
1 -4
4 4

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

19 6
11 18
12 -9
18 -5
7 14
1 16
14 -10

12 4
5 -2
6 2
1 -11
2 -10

16 1
7 1

8 7
8 3
5 2
4 8
2 5
6 6
8 -1
2 4

16 1
9 -4

5 1
2 3

2 1
1 -2

12 1
10 -6

18 3
8 11
13 -9
7 -1

1 10
1 -1
1 1
1 -1
1 1
1 -1
1 -1
1 -1
1 1
1 1
1 1

13 7
13 13
1 8
12 5
4 11
5 3
13 11
8 -8

1 1
1 1

1 1
1 -1

0 0

Code: Select all

17
0
1
1
9
10
7
3
2
16
10
16
7
15
5
1
11
16
0
11
1
0
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 11659 - Informants

Post by brianfry713 » Wed Feb 04, 2015 8:08 pm

Imagine on 11659 that "A says B and C are not reliable", "B says A is not reliable but C is reliable" and "C says A is not reliable but B is reliable". What is the maximum number of reliable informants in this case ? And why ?
Input:

Code: Select all

3 6
1 -2
1 -3
2 -1
2 3
3 -1
3 2
0 0
Correct output is 2, B and C could be reliable.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 116 (11600-11699)”