TourCounting
SRM 306 · 2006-06-08 · by Andrew_Lazarev
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
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.
{"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"}
1000000
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"}
30
100
Returns: 72
Submissions are judged against all 88 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class TourCounting with a public method int countTours(vector<string> g, int k, int m) · 88 test cases · 2 s / 256 MB per case