TopCoder problem "TourCounting" used in SRM 306 (Division I Level Three)



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

0)
    
{"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.

1)
    
{"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.
2)
    
{"NYNY",
 "NNNN",
 "YYNY",
 "NYNN"}
1000000
1000000000
Returns: 0
The graph does not have cycles.
3)
    
{"NY",
 "YN"}
1500
1
Returns: 0
Any number modulo 1 is zero.
4)
    
{"NYYNYYN",
 "YNYNYNY",
 "NYNYNYN",
 "YYYNYNY",
 "NNYYNNY",
 "NYYYNNY",
 "YYYYYYN"}
30
100
Returns: 72
5)
    
{"NYYY",
 "YNYY",
 "YYNY",
 "YNYN"}
1000
10000
Returns: 3564

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6386

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=9986&pm=6386

Writer:

soul-net

Testers:

PabloGilberto , brett1479 , Olexiy , lovro , Andrew_Lazarev

Problem categories:

Advanced Math, Dynamic Programming, Graph Theory, Recursion