Connection Status:
Competition Arena > CaterpillarSpanningTrees

CaterpillarSpanningTrees

2020 TCO Semi 2 · 2020-11-12 · by misof

2020 TCO Semi 2 · 2020-11-12 · by misof · Dynamic Programming, Graph Theory
Class Name: CaterpillarSpanningTrees
Return Type: long
Method Name: count
Arg Types: (vector<string>)
Problem Statement

Problem Statement

Time limit is 5 seconds.

Caterpillars are undirected trees in which there exists a path that contains every vertex of degree two or more.

An ASCII drawing of a sample caterpillar is shown below. Horizontal edges in the drawing show one possible path with the property mentioned above. 


                O O O         O   O   O
                 \|/          |    \ /
O --- O --- O --- O --- O --- O --- O
            |     |\          |     |
            O     O O         O     O

You are given the String[] G containing the adjacency matrix of a small undirected graph with N labeled (i.e., distinct) vertices. Count all spanning trees of this graph that are caterpillars.

Notes

  • Note that we want the exact answer, not an answer modulo something. (The total number of spanning trees of a complete graph on 16 vertices fits into a 64-bit signed integer, so there can be no overflow.)

Constraints

  • N will be between 1 and 16, inclusive.
  • G will contain N elements.
  • Each element of G will contain N characters.
  • Each character in G will be 'Y' or 'N'.
  • For each i, G[i][i] = 'N'.
  • For each i and j, G[i][j] = G[j][i].
  • The graph represented by G will be connected.
Examples
0)
{"NYNN",
 "YNYY",
 "NYNY",
 "NYYN"}
Returns: 3

The graph looks as follows: 0---1---2 \ / 3 It has three different spanning trees. Each of those is a caterpillar.

1)
{"N"}
Returns: 1

The graph consists of a single isolated vertex. Its spanning tree also consists of that one vertex. By definition, this trivial tree is also a caterpillar so we do count it.

2)
{"NYYYYYY",
 "YNYYYYY",
 "YYNYYYY",
 "YYYNYYY",
 "YYYYNYY",
 "YYYYYNY",
 "YYYYYYN"}
Returns: 15967

The complete graph on 7 vertices has 16807 different spanning trees. Almost all of them are caterpillars. The only unlabeled tree on seven vertices that is not a caterpillar is shown below. O---O---O---O---O | O | O There are 7 * 20 * 6 = 840 spanning trees of K_7 that look like this. Thus, there are 16807 - 840 distinct caterpillar spanning trees.

3)
{
"NYNNNNNNNNNNN",
"YNYNNNNNNNNNN",
"NYNYYNNNNNNNN",
"NNYNNNNNNNNNN",
"NNYNNYYYYYNNN",
"NNNNYNNNNNNNN",
"NNNNYNNNNNNNN",
"NNNNYNNNNNNNN",
"NNNNYNNNNNNNN",
"NNNNYNNNNNYYY",
"NNNNNNNNNYNNN",
"NNNNNNNNNYNNN",
"NNNNNNNNNYNNN"}
Returns: 1

This graph is the 13-vertex caterpillar shown below. 5 6 7 12 \|/ | 0 --- 1 --- 2 --- 4 --- 9 --- 11 | | | 3 8 10

4)
{"NY", "YN"}
Returns: 1

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

Coding Area

Language: C++17 · define a public class CaterpillarSpanningTrees with a public method long long count(vector<string> G) · 106 test cases · 2 s / 256 MB per case

Submitting as anonymous