Connection Status:
Competition Arena > DistanceGraph

DistanceGraph

TCO12 Championship Round · 2012-03-27 · by rng_58

TCO12 Championship Round · 2012-03-27 · by rng_58 · Dynamic Programming, Graph Theory, Greedy, Math
Class Name: DistanceGraph
Return Type: int
Method Name: countArrangements
Arg Types: (int, int, vector<string>)
Problem Statement

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).

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.

Statement by TopCoder, Inc. — view the original on the archive.

Examples
0)
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).

1)
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.

2)
5
2
{"NNYY", "NNNY", "YNNY", "YYYN"}
Returns: 4
3)
10
4
{"NYYY", "YNYY", "YYNY", "YYYN"}
Returns: 600
4)
20
6
{"NYYYN", "YNYNN", "YYNYN", "YNYNY", "NNNYN"}
Returns: 2940

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

Coding Area

Language: C++17 · define a public class DistanceGraph with a public method int countArrangements(int N, int D, vector<string> friendship) · 139 test cases · 2 s / 256 MB per case

Submitting as anonymous