DistanceGraph | Topcoder Archive

Problem Statement

Fox Ciel is the owner of a hotel. In her hotel, there are N rooms numbered from 0 to N-1. The distance between room i and room j is |i-j|.

M cats, conveniently numbered from 0 to M-1, want to stay in this hotel. You are given a String[] friendship with M elements, containing M characters each. These describe the friendship between those M cats. In particular, character j of element i of friendship is 'Y' if cats i and j are friends, and 'N' if they are not. Additionally, friendship has the following properties:

It is symmetric. Cats i and j are friends if and only if cats j and i are friends.
It is anti-reflexive. No cat is friends with itself.
The graph of friendships is connected. In other words, for any two cats i and j we can form a sequence of cats starting with cat i and ending with cat j, such that all pairs of adjacent cats are friends.

Ciel wants to assign rooms to the cats. The cats made the following requests:

Each cat must be assigned a single room.
No two cats can be assigned the same room.
For each distinct i and j, if cat i and cat j are friends, the distance between their rooms must be less than or equal to D.
For each distinct i and j, if cat i and cat j are not friends, the distance between their rooms room must be strictly more than D.

You are given the ints N and D and the String[] friendship. Let X be the number of ways in which Ciel can assign rooms to the cats, while satisfying all their requests. Compute and return the value (X modulo 1,000,000,007).

Definition

Class:: DistanceGraph
Method:: countArrangements
Parameters:: int, int, String[]
Returns:: int
Method signature:: int countArrangements(int N, int D, String[] friendship)
(be sure your method is public)

Notes

In the statement, |x| denotes the absolute value of x.

Constraints

N will be between 1 and 100, inclusive.
D will be between 1 and 8, inclusive.
friendship will contain between 1 and 50 elements, inclusive.
friendship will contain at most N elements.
Each element of friendship will contain exactly M characters, where M is the number of elements of friendship.
Each character in friendship will be either 'Y' or 'N'.
For each i and j, the j-th character of the i-th element of friendship and the i-th character of the j-th element of friendship will be the same.
For each i, the i-th character of the i-th element of friendship will be 'N'.
For each i and j, you can reach cat j from cat i by a sequence of friends, as explained in the problem statement.

Examples

```
5
```
```
2
```
```
{"NY", "YN"}
```
```
Returns: 14
```
There are two cats. As they are friends, their rooms must be at most 2 apart. There are 14 possible assignments (cat 0's room, cat 1's room): (0,1), (0,2), (1,0), (1,2), (1,3), (2,0), (2,1), (2,3), (2,4), (3,1), (3,2), (3,4), (4,2), and (4,3).
```
58
```
```
1
```
```
{"NYYY", "YNNN", "YNNN", "YNNN"}
```
```
Returns: 0
```
Cat 0 is friends with each of the other three cats. As D=1, each of the three cats should receive a room that is next to cat 0's room. This is impossible.

{"NNYY", "NNNY", "YNNY", "YYYN"}

Returns: 4

{"NYYY", "YNYY", "YYNY", "YYYN"}

Returns: 600

{"NYYYN", "YNYNN", "YYNYN", "YNYNY", "NNNYN"}

Returns: 2940

{"NYNY", "YNYN", "NYNY", "YNYN"}

Returns: 0

{"NNNNNNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNYNNYNNNNNNNN",
"NNNNYYYNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNYNNNNNNNNNYNY",
"NNNNNNNNNNYYNYNNNNNNNYNNNNNNNNNYNNNNNNNNNNNYNNYNNN",
"NNNNNNNNNNNNNNNNNYNNNNNYNNNNYNNNNYYNNNNYNNYNNNNNNN",
"NYNNNNYNNNNNYNNNYNYNYNYNNNNNNNNNNNNNYNNNNNNNNNNYNY",
"NYNNNNNNNNNNNNYNNNNYNNNNNNNNNNNNNNNNNYYNNNNNNNNNNY",
"NYNNYNNNNNNNNNNNYNYNYNNNNNNNNNNNNNNNYYNNNNNNNNNYNY",
"NNNNNNNNNNNNNNNYNYNNNNNNNNNNNNYNNNNYNNNNYNNNYNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNYYYNNYNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNYNNNYNYNNNYNNNNNNNNNYNNNYNNNNNNNNYNYYN",
"NNYNNNNNNNNYNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNYNNYNNN",
"NNYNNNNNNNYNNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNYNNYNNN",
"NNNNYNNNNYNNNNNNYNYNYNYNNNNNNNNNYNNNYNNNNNNNNYNYYN",
"NNYNNNNNNNNNNNNNNNNNNYNNNNNNNNNYNNNNNNNNNNNNNYYNYN",
"YNNNNYNNNNNNNNNNNNNYNNNNNNNYNNNNNNNNNNYNNYNNNNNNNN",
"NNNNNNNYNNNNNNNNNYNNNNNNNNNNNNYNNYNNNNNNYNYNYNNNNN",
"NNNNYNYNNYNNYNNNNNYNYNYNNNNNNNNNYNNNYNNNNNNNNYNYYN",
"NNNYNNNYNNNNNNNYNNNNNNNYNNNNNNYNNYYNNNNYYNYNNNNNNN",
"NNNNYNYNNYNNYNNNYNNNYNYNNNNNNNNNYNNNYNNNNNNNNYNYNN",
"NYNNNYNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNYYNNNNNNNNNNY",
"NYNNYNYNNNNNYNNNYNYNNNNNNNNNNNNNNNNNYYNNNNNNNNNYNY",
"NNYNNNNNNNYYNYNNNNNNNNNNNNNNNNNYNNNNNNNNNNNYNNYNNN",
"NNNNYNNNNYNNYNNNYNYNNNNNNNNNNNNNYNNNYNNNNNNNNYNYYN",
"NNNYNNNNNNNNNNNNNYNNNNNNNNNNYNYNNYYNNNNYNNYNNNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNNYYNNYNNNNNYNNNNNNNNYNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNYNYNNYNNNNNYNNNNNNNNNNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNYYNNNYNNNNNYNNNNNNNNYNNNNN",
"YNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNYNNYNNNNNNNN",
"NNNYNNNNNNNNNNNNNNNNNNNYNNNNNNNNNYYNNNNYNNYYNNNNNN",
"NNNNNNNNYNNNNNNNNNNNNNNNYYYNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNYNNNNNNNYNYNNNNNYNNNNNNNNNYNNNNNNYNYNNNNNNN",
"NNYNNNNNNNYYNYNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNYNNN",
"NNNNNNNNNYNNYNNNYNYNNNYNNNNNNNNNNNNNYNNNNNNNNYNNYN",
"NNNYNNNNNNNNNNNYNYNNNNNYNNNNYNYNNNYNNNNYYNYNNNNNNN",
"NNNYNNNNNNNNNNNNNYNNNNNYNNNNYNNNNYNNNNNYNNYNNNNNNN",
"NNNNNNNYNNNNNNNNNNNNNNNNYYYNNNNNNNNNNNNNNNNNYNNNNN",
"NNNNYNYNNYNNYNNNYNYNYNYNNNNNNNNNYNNNNNNNNNNNNNNYNY",
"NYNNNYYNNNNNNNNNNNNYYNNNNNNNNNNNNNNNNNNNNNNNNNNNNY",
"YNNNNYNNNNNNNNYNNNNYNNNNNNNYNNNNNNNNNNNNNYNNNNNNNN",
"NNNYNNNNNNNNNNNNNYNNNNNYNNNNYNNNNYYNNNNNNNYNNNNNNN",
"NNNNNNNYNNNNNNNYNYNNNNNNNNNNNNYNNYNNNNNNNNYNYNNNNN",
"YNNNNNNNNNNNNNYNNNNNNNNNNNNYNNNNNNNNNNYNNNNNNNNNNN",
"NNNYNNNNNNNNNNNYNYNNNNNYNNNNYNYNNYYNNNNYYNNNNNNNNN",
"NNYNNNNNNNYYNNNNNNNNNYNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNYNNNNNNNYNNNNNNNNYNYNNNNNNNNYNNNNYNNNNNNNNN",
"NNNNNNNNNYNNYYNNYNYNNNYNNNNNNNNNYNNNNNNNNNNNNNNNYN",
"NNYNNNNNNNYYNYNNNNNNNYNNNNNNNNNYNNNNNNNNNNNNNNNNNN",
"NYNNYNYNNYNNYNNNYNYNYNYNNNNNNNNNNNNNYNNNNNNNNNNNNY",
"NNNNNNNNNYNNYYNNYNNNNNYNNNNNNNNNYNNNNNNNNNNNNYNNNN",
"NYNNYYYNNNNNNNNNNNNYYNNNNNNNNNNNNNNNYYNNNNNNNNNYNN"}

Returns: 448127799

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.