Connection Status:
Competition Arena > GameWithGraphAndTree

GameWithGraphAndTree

Member Single Round Match 474 · 2009-12-03 · by K.A.D.R

Member Single Round Match 474 · 2009-12-03 · by K.A.D.R · Dynamic Programming
Class Name: GameWithGraphAndTree
Return Type: int
Method Name: calc
Arg Types: (vector<string>, vector<string>)
Problem Statement

Problem Statement

Little Dazdraperma likes graphs a lot. Recently she invented a new game for one person with graphs. Given a connected undirected graph with N vertices and a tree with N nodes (see the notes for definitions of all unclear terms from graph theory), she tries to place that tree on the graph in the following way:

  • Each node of the tree is put into correspondence with a vertex of the graph. Each node then corresponds to one vertex and each vertex corresponds to one node.
  • If there is an edge between two nodes of the tree then there must be an edge between the corresponding vertices in the graph.
Now Dazdraperma wonders how many ways are there to do such placement. Two placements are considered equal if each node of the tree corresponds to the same vertex of the graph in both placements. Return this number modulo 1000000007.

The graph will be represented as String[] graph where j-th character in i-th element will be 'Y' if there is an edge between vertices i and j and 'N' otherwise. The tree will be given in the same way in String[] tree.

Notes

  • For the purpose of this problem, an undirected graph can be treated as a set of vertices and a set of edges, where each edge establishes a bidirectional connection between two different vertices.
  • A path between two different vertices A and B in a graph G is a sequence of 2 or more vertices v[0] = A, v[1], ..., v[L-1] = B, such that there's an edge in G between each two adjacent vertices in this sequence.
  • A graph G is connected if there's a path between each two different vertices of G.
  • A graph G is a tree if it is connected and contains exactly V-1 edges, where V is the total number of vertices in G.

Constraints

  • graph will contain between 1 and 14 elements, inclusive.
  • tree will contain the same number of elements as graph.
  • Each element of graph will contain the same number of characters as the number of elements in graph.
  • Each element of tree will contain the same number of characters as the number of elements in tree.
  • Each character in each element of graph will be either 'Y' or 'N'.
  • Each character in each element of tree will be either 'Y' or 'N'.
  • For each i, i-th character of i-th element in both graph and tree will be equal to 'N'.
  • For each i and j, j-th character of i-th element in graph will be equal to i-th character of j-th element.
  • For each i and j, j-th character of i-th element in tree will be equal to i-th character of j-th element.
  • graph will represent a connected graph.
  • tree will represent a tree.
Examples
0)
{"NYYYYYYYYYYYYY","YNYYYYYYYYYYYY","YYNYYYYYYYYYYY","YYYNYYYYYYYYYY","YYYYNYYYYYYYYY","YYYYYNYYYYYYYY","YYYYYYNYYYYYYY","YYYYYYYNYYYYYY","YYYYYYYYNYYYYY","YYYYYYYYYNYYYY","YYYYYYYYYYNYYY","YYYYYYYYYYYNYY","YYYYYYYYYYYYNY","YYYYYYYYYYYYYN"}
{"NYYYYYYYYYYYYY","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN","YNNNNNNNNNNNNN"}
Returns: 178290591
1)
{"NY","YN"}
{"NY","YN"}
Returns: 2

There are 2 possible mappings.

2)
{"NYN",
 "YNY",
 "NYN"}
{"NYY",
 "YNN",
 "YNN"}
Returns: 2

Vertex 1 of the graph must correspond to node 0 of the tree. There remain 2 possible ways to map vertices 0 and 2 of the graph.

3)
{"NYNNN",
 "YNYYY",
 "NYNYY",
 "NYYNY",
 "NYYYN"}
{"NYNNN", 
 "YNYNN",
 "NYNYN",
 "NNYNY",
 "NNNYN"}
Returns: 12

In this case vertex 0 of the graph can correspond only to nodes 0 and 4 of the tree. If it corresponds to 0, vertex 1 of the graph must correspond to node 1 of the tree. All other vertices can be mapped in any way, so there are 3! possible mappings. There are also 3! mappings when vertex 0 of the graph corresponds to node 4 of the tree. The total number of mappings is 2*3!=12.

4)
{"NYNNNY",
 "YNYNNN",
 "NYNYNN",
 "NNYNYN", 
 "NNNYNY",
 "YNNNYN"}
{"NYNNYN",
 "YNNYNY",
 "NNNNYN",
 "NYNNNN",
 "YNYNNN",
 "NYNNNN"}
Returns: 0

There are no possible mappings in this test case.

5)
{"NYNNYN",
 "YNNYNY",
 "NNNNYN",
 "NYNNNN",
 "YNYNNN",
 "NYNNNN"}
{"NNNYYN", 
 "NNYNNN",
 "NYNNYY", 
 "YNNNNN",
 "YNYNNN",
 "NNYNNN"}
Returns: 2

The graph can also be a tree.

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

Coding Area

Language: C++17 · define a public class GameWithGraphAndTree with a public method int calc(vector<string> graph, vector<string> tree) · 104 test cases · 2 s / 256 MB per case

Submitting as anonymous