Rumor

SRM 525 · 2011-05-25 · by ir5

SRM 525 · 2011-05-25 · by ir5 · Brute Force, Graph Theory

Show categories

Class Name: Rumor

Return Type: int

Method Name: getMinimum

Arg Types: (string, vector<string>)

Problem Statement

There are N rabbits who like to gossip. They are numbered from 0 to N-1.

There are two rumors. Let's call them A and B. At this moment, each rabbit either knows both rumors or no rumors at all. The rabbits want to spread the rumors to everyone as quickly as possible.

Rabbits are very picky when it comes to spreading rumors. Each rabbit only trusts some of the other rabbits. Moreover, the situation is not necessarily symmetric - there may be rabbits A and B such that A trusts B, but B does not trust A.

At the beginning of each day, each rabbit who knows at least one rumor chooses a rumor X it knows. The rabbit then spends the day spreading rumor X. A rabbit will learn a new rumor if it is spreaded by someone it trusts. Note that a rabbit may learn both rumors in the same day (from two different other rabbits). Also note that a rabbit may spread one rumor and learn the other rumor on the same day.

You are given a String knowledge and a String[] graph. The String knowledge has exactly N characters. Character i of knowledge is 'Y' if rabbit i already knows both rumors, or 'N' if it does not know the rumors yet. The String[] graph contains N strings with N characters each. Element i of graph describes rabbits who trust rabbit i: character j of element i of graph is 'Y' if rabbit j trusts rabbit i, or 'N' if rabbit j does not trust rabbit i. In other words, graph[i][j] is 'Y' if and only if rabbit i will spread rumors to rabbit j.

Return the minimum number of days needed to spread both rumors so that each of the N rabbits will know both rumors. If it is impossible, return -1.

Constraints

knowledge will contain between 1 and 16 characters, inclusive.
Each character of knowledge will be either 'Y' or 'N'.
knowledge will contain at least one 'Y' character.
graph will contain N elements, where N is the length of knowledge.
Each element of graph will contain N characters.
Each character of graph will be either 'Y' or 'N'.
i-th character of i-th element of graph will be 'N'.

Examples

"YNN"
{"NYN"
,"NNY"
,"NNN"}
Returns: 3

Initially, there are 3 rabbits. Rabbit 0 knows rumor A and B, and other rabbits know nothing. One of the optimal ways is as follows. On day 1, rabbit 0 sends information about rumor A to rabbit 1. On day 2, rabbit 1 sends information about rumor A to rabbit 2, and rabbit 0 sends information about rumor B to rabbit 1. On day 3, rabbit 1 sends information about rumor B to rabbit 2. As a result, it takes 3 days.

"YNNY"
{"NYYN"
,"YNNY"
,"YNNY"
,"NYYN"}
Returns: 1

One of the optimal ways is as follows. On day 1, rabbit 0 sends information about rumor A to rabbit 1 and rabbit 2, and rabbit 3 sends information about rumor B to rabbit 1 and rabbit 2.

"YYYY"
{"NYNN"
,"YNYN"
,"NYNY"
,"NNYN"}
Returns: 0

All rabbits already know the rumors, so no day is required.

"YYYYYN"
{"NYYYYN"
,"YNYYYN"
,"YYNYYN"
,"YYYNYN"
,"YYYYNN"
,"NNNNNN"}
Returns: -1

It is impossible to make rabbit 5 know the rumors.

"NNNY"
{"NNNN"
,"YNNN"
,"YNNN"
,"NYYN"}
Returns: 3

"Y"
{"N"}
Returns: 0

minimal test

"YYYNNNN"
{"NYYNNNN"
,"YNYNNNN"
,"YYNNNNN"
,"YYYNYYY"
,"YYYYNYY"
,"YYYYYNY"
,"YYYYYYN"}
Returns: -1

destroy solutions which do not do bfs or dfs to check the connection of graph

19)

"YNNNNNNNNNNNNNNN"
{"NYNNNNNNNNNNNNNN"
,"NNYNNNNNNNNNNNNN"
,"NNNYNNNNNNNNNNNN"
,"NNNNYNNNNNNNNNNN"
,"NNNNNYNNNNNNNNNN"
,"NNNNNNYNNNNNNNNN"
,"NNNNNNNYNNNNNNNN"
,"NNNNNNNNYNNNNNNN"
,"NNNNNNNNNYNNNNNN"
,"NNNNNNNNNNYNNNNN"
,"NNNNNNNNNNNYNNNN"
,"NNNNNNNNNNNNYNNN"
,"NNNNNNNNNNNNNYNN"
,"NNNNNNNNNNNNNNYN"
,"NNNNNNNNNNNNNNNY"
,"NNNNNNNNNNNNNNNN"}
Returns: 16

straight line

Submissions are judged against all 127 archived test cases, of which 8 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class Rumor with a public method int getMinimum(string knowledge, vector<string> graph) · 127 test cases · 2 s / 256 MB per case