Connection Status:
Competition Arena > BigO

BigO

SRM 608 · 2013-12-22 · by rng_58

SRM 608 · 2013-12-22 · by rng_58 · Dynamic Programming, Graph Theory
Class Name: BigO
Return Type: int
Method Name: minK
Arg Types: (vector<string>)
Problem Statement

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. 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.

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)
{"NYYN",
 "YNNN",
 "NNNY",
 "NNYN"}
Returns: 1
4)
{"NYYYNYYYNNYYYYYYNYNN",
 "NNNNYNYYNNYYYNYYNYYN",
 "NYNNYYYNNNYYYYNYNYNN",
 "NYYNNYYYYNNNYYNNYNYY",
 "NYNYNNNNNNYYYYYNYYYN",
 "YNNNNNNYNNYNNYYYYYYY",
 "NNYYNNNNNYNYNYNNYNYY",
 "NNYNYYNNNNYNYNYYYYNN",
 "NYYNYYNNNYNNYYYNYNYN",
 "YYNNYNNYYNYNNNNNYNNN",
 "YYNYYNNYYYNYYNYNYYYY",
 "YYNNYYNYNYNNNNYNNNNY",
 "NNYYNYYYNNNNNYYYYYNY",
 "YNNNYNNNNYNNNNNYNNNY",
 "YYYYNYYNNYNNNNNYNNNN",
 "NYYYYNYNYYNNYNNNYNNY",
 "YYYYYNNNYYYYNYYYNNYN",
 "NNYNNYNYNYNNNNNNYNYN",
 "YYNYYNNNNNYNNYNYNNNY",
 "YYYYNYNYYNNYNYNYNNNN"}
Returns: -1

Submissions are judged against all 114 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class BigO with a public method int minK(vector<string> graph) · 114 test cases · 2 s / 256 MB per case

Submitting as anonymous