CoprimeMatrix
TCO17 Round 3A · 2017-03-31 · by cgy4ever
TCO17 Round 3A · 2017-03-31 · by cgy4ever · Math
Problem Statement
Problem Statement
Two positive integers are called coprime if their greatest common divisor is 1.
For example, 12 and 35 are coprime but 18 and 33 are not, as they are both divisible by 3.
You are given aString[] coprime with n elements.
Each element of coprime is a string of n characters, and each of those is either 'Y' or 'N'.
Bear Limak is looking for a sequence of n positive integers. The sequence must be increasing and the integers have to be consecutive. In other words, if we denote the elements x[0], x[1], ..., x[n-1], we should have x[i+1] = x[i] + 1 for all valid i.
Additionally, Limak's sequence must match coprime in the following way: for each valid i and j, coprime[i][j] = 'Y' if and only if x[i] and x[j] are coprime.
Please return "Possible" if such a sequence exists and "Impossible" if there is no such sequence.
You are given a
Bear Limak is looking for a sequence of n positive integers. The sequence must be increasing and the integers have to be consecutive. In other words, if we denote the elements x[0], x[1], ..., x[n-1], we should have x[i+1] = x[i] + 1 for all valid i.
Additionally, Limak's sequence must match coprime in the following way: for each valid i and j, coprime[i][j] = 'Y' if and only if x[i] and x[j] are coprime.
Please return "Possible" if such a sequence exists and "Impossible" if there is no such sequence.
Constraints
- n will be between 1 and 50, inclusive.
- coprime will contain exactly n elements.
- Each element in coprime will contian exactly n characters.
- Each character in coprime will be 'Y' or 'N'.
Examples
0)
{"NYNYN",
"YNYYN",
"NYNYN",
"YYYNY",
"NNNYN"}
Returns: "Possible"
It is possible, for example, if x = {2,3,4,5,6} then we have: 2 3 4 5 6 2 N Y N Y N 3 Y N Y Y N 4 N Y N Y N 5 Y Y Y N Y 6 N N N Y N
1)
{"NY",
"NN"}
Returns: "Impossible"
It is impossible: coprime[0][1] and coprime[1][0] should be equal.
2)
{"NYYYYN",
"YNYNNN",
"YYNYYY",
"YNYNYN",
"YNYYNY",
"NNYNYN"}
Returns: "Possible"
3)
{"NN",
"NN"}
Returns: "Impossible"
4)
{"YY",
"YY"}
Returns: "Impossible"
Submissions are judged against all 228 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class CoprimeMatrix with a public method string isPossible(vector<string> coprime) · 228 test cases · 2 s / 256 MB per case