Connection Status:
Competition Arena > TreeCount

TreeCount

SRM 413 · 2008-08-05 · by yuhch123

SRM 413 · 2008-08-05 · by yuhch123 · Dynamic Programming
Class Name: TreeCount
Return Type: int[]
Method Name: count
Arg Types: (vector<string>)
Problem Statement

Problem Statement

In graph theory, an independent set or stable set is a set of vertices in a graph such that no two of the vertices are adjacent. That is, it is a set V of vertices such that for every two vertices in V, there is no edge connecting the two.

Similarly, we can define a k-stable set as a set of vertices in a graph such that each vertex in the set has at most k adjacent vertices that are also in the set. So the 0-stable set is the original stable set.

You will be given a String[] graph, representing an undirected, acyclic, connected graph. The j-th character of the i-th element of graph will be 'Y' if vertices i and j are connected, or 'N' otherwise. Return a int[] containing exactly n elements, where n is the number of elements in graph. The i-th element should be the number of distinct i-stable sets in the graph modulo 112901989, where i is a 0-based index.

Constraints

  • graph will contain between 1 and 50 elements, inclusive.
  • Each element of graph will contain exactly N characters, where N is the number of elements in graph.
  • Each character in graph will be either 'Y' or 'N'.
  • The j-th character of the i-th element of graph will equal to the i-th character of the j-th element.
  • The i-th character of the i-th element of graph will be 'N'.
  • The graph will represent a tree.
Examples
0)
{"NYY", "YNN", "YNN"}
Returns: {5, 7, 8 }

The tree is 1-0-2. The 5 0-stable sets are {}, {0}, {1}, {2}, {1, 2}. The 7 1-stable sets are all the subsets except {0, 1, 2}. There are 2^3 subsets total, and each one is a 2-stable set.

1)
{"N"}
Returns: {2 }
2)
{"NYNNNYY", "YNNNNNN", "NNNNNNY", "NNNNNNY", "NNNNNNY", "YNNNNNN", "YNYYYNN"}
Returns: {44, 73, 104, 124, 128, 128, 128 }
3)
{"NY", "YN"}
Returns: {3, 4 }
4)
{"NYYYYY", "YNNNNN", "YNNNNN", "YNNNNN", "YNNNNN", "YNNNNN"}
Returns: {33, 38, 48, 58, 63, 64 }

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

Coding Area

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

Submitting as anonymous