BigOEasy
SRM 608 · 2013-12-22 · by rng_58
SRM 608 · 2013-12-22 · by rng_58 · Graph Theory
Problem Statement
Problem Statement
Cat Snuke received a directed graph as a present.
You are given aString[] 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
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.
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
0)
{"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.
1)
{"NYYN",
"NNNY",
"NNNY",
"NNNN"}
Returns: "Bounded"
The number of walks in this graph is finite.
2)
{"NYN",
"NNY",
"YNN"}
Returns: "Bounded"
3)
{"NYYN",
"YNNN",
"NNNY",
"NNYN"}
Returns: "Bounded"
4)
{"NYY",
"YNN",
"YNN"}
Returns: "Unbounded"
Submissions are judged against all 96 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class BigOEasy with a public method string isBounded(vector<string> graph) · 96 test cases · 2 s / 256 MB per case