TourCounting | Topcoder Archive

Problem Statement

You are given a directed graph g, and you must determine the number of distinct cycles in g that have length less than k. Since this number can be really big, return the answer modulo m. A cycle is a non-empty sequence of nodes (not necessarily distinct) in which there is an edge from each node to the next node, and an edge from the last node in the sequence to the first node. Two cycles are distinct if their sequences are not identical. See example 0 for further clarification.

g will be given as a String[] where the jth character of the ith element indicates whether there is an edge from node i to node j ('Y' means there is one, and 'N' means there is not).

Definition

Class:: TourCounting
Method:: countTours
Parameters:: String[], int, int
Returns:: int
Method signature:: int countTours(String[] g, int k, int m)
(be sure your method is public)

Notes

The answer modulo m means that you must return the remainder of dividing the result by m.

Constraints

g will have between 1 and 35 elements, inclusive.
Each element of g will have exactly N characters, where N is the number of elements in g.
Each character of each element of g will be 'Y' or 'N'.
The ith character of the ith element of g will be 'N'.
k will be between 1 and 1000000 (106), inclusive.
m will be between 1 and 1000000000 (109), inclusive.

Examples

```
{"NYNY",
 "NNYN",
 "YNNN",
 "YNNN"}
```
```
6
```
```
100
```
```
Returns: 12
```
The possible cycles with length less than 6 are: (0,3) ; (3,0) ; (0,1,2) ; (1,2,0) ; (2,0,1) (0,3,0,3) ; (3,0,3,0) ; (0,1,2,0,3) ; (0,3,0,1,2) (1,2,0,3,0) ; (2,0,3,0,1) ; (3,0,1,2,0) Note that (0,3), (3,0) and (0,3,0,3) are all considered different.
```
{"NYNNNNN",
 "NNYNNNN",
 "NNNYNNN",
 "NNNNYNN",
 "NNNNNYN",
 "NNNNNNY",
 "YNNNNNN"}
```
```
40
```
```
13
```
```
Returns: 9
```
All cycles have lengths that are multiples of 7. For each starting node and each multiple of 7 there exists one cycle. There are 5 non-zero multiples of 7 that are less than 40 (7,14,21,28,35) and 7 possible starting nodes. Therefore, the total number of cycles is 5x7=35. 35 modulo 13 is 9.

{"NYNY",
 "NNNN",
 "YYNY",
 "NYNN"}

1000000000

Returns: 0

The graph does not have cycles.

```
{"NY",
 "YN"}
```
```
1500
```
```
1
```
```
Returns: 0
```
Any number modulo 1 is zero.

{"NYYNYYN",
 "YNYNYNY",
 "NYNYNYN",
 "YYYNYNY",
 "NNYYNNY",
 "NYYYNNY",
 "YYYYYYN"}

Returns: 72

{"NYYY",
 "YNYY",
 "YYNY",
 "YNYN"}

Returns: 3564

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.