BannedBook
SRM 766 · 2019-09-09 · by misof
Problem Statement
A group of n people (numbered 0 through n-1) is interested in a banned book.
You have one copy of the book and you can deliver it to any one of those people. They will then pass the book around among themselves, until everyone had a chance to read the book.
Of course, passing a banned book from one person to another is always risky. Thus, the first priority is to minimize the number of passes -- i.e., each person must only hold the book exactly once.
Passing of a book is considered low-risk if somebody passes the book to a) their friend, b) a friend of a friend, or c) a friend of a friend of a friend. All other passes are considered high-risk.
You are given information on friendship among the n people: friend[x][y] is 'Y' if people x and y are friends, and 'N' otherwise.
Among all ways of passing the book as described above we are interested in those that have as few high-risk passes as possible. Determine and return any such order.
Constraints
- n will be between 1 and 50, inclusive.
- friend will contain n elements, each containing n characters.
- Each character in friend will be 'Y' or 'N'.
- For each x, friend[x][x] will be 'Y'.
- For each distinct x and y, friend[x][y] will equal friend[y][x].
{"YNN",
"NYN",
"NNY"}
Returns: {0, 1, 2 }
Three people who do not know each other. Each pass is high-risk. Each sequence of passes is optimal.
{"YYYYY",
"YYNNN",
"YNYNN",
"YNNYN",
"YNNNY"}
Returns: {0, 1, 2, 3, 4 }
Five people. Everybody knows person 0, so all passes are low-risk. Again, each sequence of passes is optimal.
{"YYNNN",
"YYYNN",
"NYYYN",
"NNYYY",
"NNNYY"}
Returns: {0, 2, 4, 3, 1 }
Five people who live along a street. Everyone is friends with their neighbors. It is possible to share the book in such a way that each pass is low-risk, but not all sequences work. In particular, person 0 cannot pass the book directly to person 4 or vice versa.
{"YYNNYNYNN",
"YYNNNYNNN",
"NNYNNNNNN",
"NNNYNNNNN",
"YNNNYNNNY",
"NYNNNYNYN",
"YNNNNNYNY",
"NNNNNYNYN",
"NNNNYNYNY"}
Returns: {0, 5, 7, 1, 8, 6, 4, 2, 3 }
{"YNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNYNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNN", "NNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNYNNNNNNNNNYNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNN", "NNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNYNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNYNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNN", "NNYNNNNNNNNNYNYYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNY", "NNNNNNYNNNNNNNNNYNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNN", "NNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "YNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNYNNNNN", "NNNNNNNNNNNNNNNNNNNNNNYNNNNNYNNNNNYNNNYNNNNNNNNNNN", "NNNNNNYNNNNNNNNNNNNNNNNYNNNNNNNNNNNYNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNY", "NNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNYNNNNNYNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNYNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYYNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYNNNNNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNYNNNNNNNNNNNYNNN", "NNNNNNNNNNNNNNNNYNNNNYNYNNNNNNNNNNNYNNNNNNNNNNNNNN", "NNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNYNNNNNNNNNNNYN", "NNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNYNNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNN", "NNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNN", "NNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNN", "NNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNYYNNNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYYNNNN", "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNYNNN", "NNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNYN", "NNNNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNY"}
Returns: {0, 20, 1, 2, 12, 14, 41, 49, 26, 15, 27, 48, 36, 34, 28, 38, 22, 33, 32, 46, 3, 4, 5, 6, 35, 8, 44, 45, 21, 23, 16, 7, 47, 9, 10, 11, 13, 30, 17, 18, 43, 19, 24, 37, 25, 29, 31, 39, 40, 42 }
Submissions are judged against all 104 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class BannedBook with a public method vector<int> passAround(vector<string> friend) · 104 test cases · 2 s / 256 MB per case