CoprimeMatrix | Topcoder Archive

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 a String[] 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.

Definition

Class:: CoprimeMatrix
Method:: isPossible
Parameters:: String[]
Returns:: String
Method signature:: String isPossible(String[] coprime)
(be sure your method is public)

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

```
{"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
```
{"NY",
 "NN"}
```
```
Returns: "Impossible"
```
It is impossible: coprime[0][1] and coprime[1][0] should be equal.

{"NYYYYN",
 "YNYNNN",
 "YYNYYY",
 "YNYNYN",
 "YNYYNY",
 "NNYNYN"}

Returns: "Possible"

```
{"NN",
 "NN"}
```
```
Returns: "Impossible"
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.