PROBLEM STATEMENT
Cat Snuke received a directed graph as a present.
You are given a vector graph. The number of elements in graph is the number of vertices
of the graph he received. If there is an edge from the vertex i (0-based) to the vertex j, the
j-th character of the i-th element of graph is 'Y'. Otherwise the j-th character of the i-th
element of graph is 'N'.
Cat Snuke wonders how many walks of length L are there when L is very big. Return the minimal
nonnegative integer K such that the number of walks of length L is O(L^K). If there is no such K,
return -1 instead.
See notes for formal definitions of walks and big-O notation.
DEFINITION
Class:BigO
Method:minK
Parameters:vector
Returns:int
Method signature:int minK(vector graph)
NOTES
-A sequence of vertices v_0, v_1, ..., v_L is called a walk of length L if for each i between 0
and L-1, inclusive, there exists an edge from vertex v_i to v_(i+1). Note that a walk may use each
edge of the graph arbitrarily many times.
-The number of walks of length L is O(L^K) iff the following condition holds: There exists a
constant C such that for any positive integer L the number of walks of length L is at most C * L^K.
CONSTRAINTS
-graph will contain between 2 and 50 elements, inclusive.
-Each element of graph will contain exactly V characters, where V is the number of elements of
graph.
-Each character in graph will be either 'Y' or 'N'.
-For each i, the i-th character of the i-th element of graph will be 'N'.
EXAMPLES
0)
{"NYY",
"YNY",
"YYN"}
Returns: -1
For this graph there are exactly 3*2^L walks of length L. There is no K such that 3*2^L is O(L^K).
1)
{"NYNNN",
"NNYNN",
"NNNYN",
"NNNNY",
"NNNNN"}
Returns: 0
The number of walks of length L is zero when L is big enough.
2)
{"NYNNN",
"YNNNN",
"NNNYN",
"NNNNY",
"NNYNN"}
Returns: 0
The number of walks of length L is 5 for any L.
3)
{"NYYYNYYYNNYYYYYYNYNN",
"NNNNYNYYNNYYYNYYNYYN",
"NYNNYYYNNNYYYYNYNYNN",
"NYYNNYYYYNNNYYNNYNYY",
"NYNYNNNNNNYYYYYNYYYN",
"YNNNNNNYNNYNNYYYYYYY",
"NNYYNNNNNYNYNYNNYNYY",
"NNYNYYNNNNYNYNYYYYNN",
"NYYNYYNNNYNNYYYNYNYN",
"YYNNYNNYYNYNNNNNYNNN",
"YYNYYNNYYYNYYNYNYYYY",
"YYNNYYNYNYNNNNYNNNNY",
"NNYYNYYYNNNNNYYYYYNY",
"YNNNYNNNNYNNNNNYNNNY",
"YYYYNYYNNYNNNNNYNNNN",
"NYYYYNYNYYNNYNNNYNNY",
"YYYYYNNNYYYYNYYYNNYN",
"NNYNNYNYNYNNNNNNYNYN",
"YYNYYNNNNNYNNYNYNNNY",
"YYYYNYNYYNNYNYNYNNNN"}
Returns: -1
4)
{"NYNYYYNYYYNYYNYYNYYNYYNYNNYYYYNNNYYNNNYNYYNYNNNYNY",
"NNNNNNNNNNNNNNNNYNNNYNNNNNYNYNYNNNNNNYNNNNNNNNNNNN",
"NYNYYYYNYNYYNNYYYYYYYYYYNYYYNYYYYYYNNYYYYYYYNNYYYY",
"NYNNYYNNNNNNNNNNNYNNNYNYNNYNYNYYNYYNNYYYNNNNNNNYYY",
"NNNNNNNNNNNNYNNYYNNNYNNNNYNNYNNYNNYNNYNYNNNNNNNYYN",
"NNNNNNNNNNNNNNNNYNNNYNNNNNNNNNYNNNNNNYNNNNNNNNNNNN",
"YYNYNNNYNYYYYNYYYYYYYYYYNYYYYYYYNYYNNYNYYYYYNNYNYY",
"NYNYYNNNYYNNYNNYYYNNYYNYNYYNYYYNNNYNNYYYNNNNNNNYYY",
"NYNYYYNYNYNNNNNYYYNNNNNNNYYNYYYYNYYNNYYYNNNNNNNYYY",
"NYNNNYNNNNNNNNNYYNNNYNNNNNYNYNYNNYYNNYNYNNNYNNNNYN",
"NYNYYYNNYYNYYNYNYYNYYYNYNYYNYYYYNYNNNNYYYYNYNNNYNY",
"NYNNYYNNNYNNYNNYYYNNYYNNNYYNYYNNNYYNNNNYNNNYNNNYYY",
"NNNNNNNNNNNNNNNYYNNNYNNNNNNNYNNYNYNNNYYNNNNNNNNYNN",
"YYYYNYYYYYYYYNYYYYNYYYYYYYYYYYNYYNYYYNYYYYYNNYYNYN",
"NYNYYNNYYYNYYNNYYYNYNYNYNYYNYYYYNYYNNYYYYYNYNNNNNY",
"NYNNNNNNNNNNNNNNYNNNYNNNNNYNYNYYNYNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN",
"NYNNNYNNNNNNNNNYYNNNNNNNNNNNYNYYNYYNNYNNNNNNNNNYYN",
"NYNYYYNNYYNYNNYYYYNYYYNYNYYYYNNYNNYNNYNYYYYNNNYYYY",
"NNNYYYNNNYNYYNNYYYNNYYNNNYYNYYYYNYYNNNYYNYNYNNNYYY",
"NNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNN",
"NYNNNYNNNNNNNNNYNNNNNNNNNYYNYYYYNYYNNYNNNNNNNNNYYN",
"YYNYYYNNYYNYYNYNYYNYNYNYNYYYYYYYNYNNNYYYYYNYNNYYYY",
"NYNYYYNNNNNNYNNNYYNNYYNNNYYNYYYYNYYNNYYYNNNNNNNYNY",
"YNNNYYYYYYYYYNYYYYYYYYYNNYYNYNYNYNNYYYYYYYNYNNYYYY",
"NYNNNYNNNNNNNNNYYNNNYNNNNNYNYNYYNYYNNNNYNNNNNNNYNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNN",
"NYNYYYNYYYNYNNNNYYNYYNNYNYYNYYYYNYYNNNNNYYNYNNYYNN",
"NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNN",
"NYNNNYNNNNNNNNNYYNNNYNNNNNNNNNYYNYYNNNNYNNNNNNNYYY",
"NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNYNNNYNNNNNYNNNYNNNNNNNNNNNNNNNNNNN",
"NYNYYNNYYYNNNNNYYYNYYYNNNYYYYYYYNYYNNYYYYNNYNNNNYY",
"NNNNNNNNNNNNNNNYYNNNYNNNNNYNYNYYNNNNNYNNNNNNNNNNNN",
"NYNNNNNNNNNNNNNNYNNNYNNNNNYNNNYYNNNNNNNNNNNNNNNYNN",
"NYNYYYYYNYYYYNYYYYYYNYYYNNNYYYYYNYYNYNYYYYYYNYYYNY",
"YYNYYYNYYYNNNNNYNYYYYNYNNNYYYYYYNYYNNYYNYNNYNNYNNY",
"NNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNN",
"NYNNNYNNNNNNNNNYYNNNNYNNNNYNYNNYNNNNNYNYNNNNNNNYNN",
"NYNNNYNNNNNNNNNYYNNNNNNNNYYNYNYNNYYNNNNNNNNNNNNYNN",
"NYNYYYNYYYNYNNNNNYNNYYNYNNYNNYYYNYYNNYYYNNNNNNNYYY",
"NYNYYNNNNYNYYNNYYYNYYYNNNYYNYYYNNYYNNYYYNNNYNNNNYY",
"NYNYNYNYYYNYYNYYNYNYNYYYNNYYYYYYNNNNNYYYNYNYNNYNYY",
"NYNNNYNNNYNNNNNYYYNNYNNNNNYNYNNNNYYNNYNYNNNNNNNYYN",
"YYYNNYNYYYNYNNYYYYYNYYNYNYYYYYNYYNYNYYYYYNNYNNYNYN",
"YYNNYYYYYYYNYNYYNYYYYYYYYYYNYYYNYYYNNYYYYNYYNNYYYY",
"NYNNYYNYYYNNYNNYYYNYNYNYNYYNNYYNNYNNNYYYNYNYNNNNYY",
"NNNNNNNNNNNNNNNNYNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNN",
"NNNNNNNNNNNNNNNNNNNNYNNNNNYNYNYNNNNNNYNNNNNNNNNYNN",
"NYNNYYNNNNNNNNNYYNNNNNNNNYYNYNNYNYYNNYNYNNNNNNNYNN"}
Returns: 7
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)2010, TopCoder, Inc. All rights reserved.