Problem Statement
Cat Snuke received a directed graph as a present.
You are given a String[] 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. Can the number of walks of length L be bounded by a polynomial function of L? In other word, is there a polynomial P such that for any positive integer L the number of walks of length L is at most P(L)? Return "Bounded" if such a polynomial exists and "Unbounded" otherwise.
See notes for a formal definition of walks.
You are given a String[] 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. Can the number of walks of length L be bounded by a polynomial function of L? In other word, is there a polynomial P such that for any positive integer L the number of walks of length L is at most P(L)? Return "Bounded" if such a polynomial exists and "Unbounded" otherwise.
See notes for a formal definition of walks.
Definition
- Class:
- BigOEasy
- Method:
- isBounded
- Parameters:
- String[]
- Returns:
- String
- Method signature:
- String isBounded(String[] graph)
- (be sure your method is public)
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.
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
{"NYY", "YNY", "YYN"}Returns: "Unbounded"
For this graph there are exactly 3*2^L walks of length L. There is no polynomial that grows that quickly.{"NYYN", "NNNY", "NNNY", "NNNN"}Returns: "Bounded"
The number of walks in this graph is finite.{"NYN", "NNY", "YNN"}Returns: "Bounded"
{"NYYN", "YNNN", "NNNY", "NNYN"}Returns: "Bounded"
{"NYY", "YNN", "YNN"}Returns: "Unbounded"
{"NYNYN", "NNYNY", "YNNNN", "NNNNN", "YNNNN"}Returns: "Unbounded"
{"NYYN", "NNYN", "NNNY", "YNNN"}Returns: "Unbounded"
{"NYYNNNNYNNYNYNNNNYYNNYNYNNNNNNNNNNYNNNNNNNYYNYNNNN", "NNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "YYYNYYNYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYYYNYYYYYNYYN", "YYYNNNNYNNYNYNNNNYYNNNNYNNNNNNNNNNYNNNNNNNYYNYNNNN", "YYYNYNNYNNYYYNNNYYYNNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "YYYYYYNYYYYYYYYYYYYYYYYYYNYNYYYYYYYYYYYYNYYYYYNYYN", "NYYNNNNNNNYNYNNNNYNNNNNYNNNNNNNNNNNNNNNNNNYNNYNNNN", "YYYNYNNYNNYYYNNNNYYNNYNYNNYNYYYYYYYYYYNYNYYYNYNYNN", "YYYNYNNYNNYYYNNNNYYNYYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "NNNNNNNNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNN", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNNNNNNNYYNNNNNNYYNYNNNN", "NNNNNNNNNNNNNNNNNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "YYYNYNNYYNYYYNNNNYYNNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "YYYNYNNYNNYYYNNNNYYYNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "YYYNYNNYNNYYYNNNNYYNNYYYNNYNYYYNYYYYYYNYNYYYNYNYNN", "YYYNYNNYNYYYYNNNNYYNNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "NNYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "NYYNNNNNNNYNYNNNNYNNNNNYNNNNNNNNNNYNNNNNNNNNNYNNNN", "YYYNYNNYNNYYYNNNNYYNNYNYNNYNYYYNYYYYYYYYNYYYNYNYNN", "YYYNYNNYNNYYYNNNNYYNNYNYYNYNYYYNYYYYYYNYNYYYNYNYNN", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNNNYNNNYNNNNNNNYYNYNNNN", "YYYNYYNYNNYYYNNNNYYNNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "NNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNYNNNN", "YYYNYNNYNNYYYYNNNYYNNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "YYYNYYNYYYYYYYYYYYYYYYYYYNYNYYYYYYYYYYYYNYYYYYNYYY", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNYNNNNNYNNNNNNNYYNYNNNN", "YYYNYYNYYYYYYYYYYYYYYYYYYNYNYYYYYYYYYYYYYYYYYYNYYN", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNNNNNNNYNNNNNNNYYNYNYNN", "NYYNNNNYNNYYYNNNNYYNNNNYNNNNNNNNNNYNNNNNNNYYNYNNNN", "NYYNNNNYNNYNYNNNNYYNNNNYNNYNNNNNNNYNNNNNNNYYNYNNNN", "YYYNYNNYNNYYYNYNNYYNNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "YYYNYNNYNNYYYNNNNYYNNYNYNNYNYYYNNYYYNYNYNYYYNYNYNN", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNNNNNNNYNNNNYNNYYNYNNNN", "NYYNNNNYNNYNYNNNNYNNNNNYNNNNNNNNNNNNNNNNNNNNNYNNNN", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNNNNNNYYNNNNNNNYYNYNNNN", "YYYNYNNYNNYYYNNNNYYNNYNYNNYNYYYNYYYYNNNYNYYYNYNYNN", "YYYNYNNYNNYYYNNNNYYNNYNYNNYNYYYNNYYYYNNYNYYYNYNYNN", "YYYNYNNYNNYYYNNYNYYNNYNYNNYNYYYNYYYYYYNYNYYYNYNYNN", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNNNNNNNYNNNNNNYYYNYNNNN", "YYYNYYNYYYYYYYYYYYYYYYYYYNYNYYYYYYYYYYYYNYYYYYYYYN", "NYYNYNNYNNYNYNNNNYYNNNNYNNNNNNNNNNYNNNNNNNYYNYNNNN", "NYYNNNNNNNYNYNNNNYNNNNNYNNNNNNNNNNNNNNNNNNNYNYNNNN", "NYYNNNNNNNYNYNNNNYYNNNNYNNNNNNNNNNNNNNNNNNNNNYNNNN", "YYYNYYNYYYYYYYYYYYYYYYYYYNYNYYYYYYYYYYYYNYYYNYNYNN", "NYNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNNN", "YYYNYYNYYYYYYYYYYYYYYYYYYYYNYYYYYYYYYYYYNYYYYYNYYN", "NYYNNNNYNNYNYNNNNYYNNNNYNNNNNYNNNNYNNNNNNNYYNYNNNN", "YYYNYYNYYYYYYYYYYYYYYYYYYNYNYYYYYYYYYYYYNYYYYYNYNN", "YYYNYYYYYYYYYYYYYYYYYYYYYNYNYYYYYYYYYYYYNYYYYYNYYN"}Returns: "Bounded"
Back to all problems