RainbowGraph
SRM 720 · 2017-07-25 · by lg5293
Problem Statement
Cat Noku has a simple undirected graph with n nodes, numbered 0 through n-1.
You are given the
A walk in the graph is a sequence of nodes in which each pair of consecutive nodes is connected by an edge. Cat Noku would like to visit all nodes in the graph. More precisely, he is looking for a walk with the following properties:
- The walk visits each node exactly once.
- The walk may start and end in any node of the graph.
- Suppose the visited nodes are c1, c2, ..., cn, in this order. Whenever ci and cj have the same color, all nodes visited between ci and cj must also have that color. (Formally, for each k between i and j, node ck must have the same color as ci and cj.)
Help Cat Noku count the number of valid walks. Since this number can get very large, return it modulo 10^9+7.
Constraints
- color will have between 2 and 100 elements, inclusive.
- Each element of color will be between 0 and 9, inclusive.
- Each number from 0 to 9 will occur at most 10 times as an element of color.
- a,b will contain between 1 and 2500 elements, inclusive.
- The edges (a[i], b[i]) will describe a simple undirected graph.
{0,0,0,1,1,1,2,2,2}
{0,1,2,3,4,5,6,7,8,0,3,6}
{1,2,0,4,5,3,7,8,6,3,6,0}
Returns: 0
In this case, there are no valid walks.
{0,0,0,1,1,1,2,2,2}
{0,1,2,3,4,5,6,7,8,0,4,8}
{1,2,0,4,5,3,7,8,6,3,7,2}
Returns: 24
For example, a valid walk is 1,0,2,6,8,7,4,5,3. An example of an invalid walk would be 3,0,1,2,6,8,4,5, since even though it is a walk that visits each node exactly once, it does not satisfy the color constraint since the first and last nodes are the same color, but some middle nodes are not the same color.
{0,3,9,8,6,4}
{0,0,0,0,0,1,1,1,1,2,2,2,3,3,4}
{1,2,3,4,5,2,3,4,5,3,4,5,4,5,5}
Returns: 720
In this case, any permutation of nodes forms a valid walk.
{0,0,0,0,3,3,3,6,6,9}
{9,9,9,9,9,9,9,9,9,7,7,7,7,7,7,7,4,4,4,4,0,1,2,4,5,8}
{0,1,2,3,4,5,6,7,8,0,1,2,3,4,5,6,0,1,2,3,1,2,3,5,6,7}
Returns: 64
{3,1,4,1,5,9,2,6,5,3,5}
{1}
{2}
Returns: 0
{2, 4, 3, 0, 2, 3, 3, 3, 4, 2, 1, 2, 0, 0, 4, 1, 1, 0, 4, 4, 1, 0, 3, 2, 1}
{5, 7, 23, 20, 10, 9, 23, 7, 7, 17, 0, 20, 1, 24, 7, 5, 11, 13, 14, 9, 0, 13, 4, 9, 5,
24, 22, 24, 14, 12, 7, 4, 6, 19, 13, 5, 6, 10, 0, 2, 6, 20, 22, 2, 10, 19, 2, 24, 21,
20, 21, 2, 23, 24, 9, 19, 19, 21, 22, 2, 7, 14, 13, 12, 2, 11, 19, 12, 0, 8, 8, 1,
18, 20, 10, 1, 13, 21, 14, 1, 18, 21, 13, 15, 14, 15, 7, 6, 21, 10, 6, 24, 21, 4, 24,
3, 2, 18, 1, 24, 6, 20, 8, 16, 0, 12, 5, 11, 4, 13, 3, 16, 19, 15, 24, 24, 16, 20, 13,
18, 5, 4, 6, 23, 8, 6, 18, 15, 19, 3, 16, 17, 18, 10, 14, 14, 23, 6, 13, 7, 13, 18, 10,
19, 22, 18, 23, 5, 16, 17, 23, 4, 14, 24, 5, 20, 11, 3, 17, 23, 12, 6, 22, 8, 4, 17, 16,
8, 17, 17, 1, 4, 6, 7, 17, 17, 21, 23, 0, 15, 21, 16, 12, 20, 19, 23, 7, 21, 18, 5, 24,
24, 8, 6, 5, 9, 21, 15, 8, 11, 10, 19, 5, 24, 19, 10, 11, 0, 23, 12, 15, 18, 20, 10, 15,
13, 3, 18, 6, 22, 0, 4, 24, 19, 16, 0, 17, 7, 4, 0, 9, 4, 10, 0, 23, 16, 17, 8, 5, 12,
22, 11, 11, 5, 13, 5, 4, 20, 17, 20, 0, 10, 4, 18, 3, 3, 6, 21, 9, 7, 18, 1, 14, 5, 20,
10, 12, 20, 9, 15, 18, 5, 12, 11, 11, 20, 11, 15, 6, 2, 6, 19, 13, 15, 15, 21, 22, 9, 19,
16, 8, 9, 15, 8, 21, 22, 19, 18, 9, 2}
{21, 1, 11, 19, 24, 1, 7, 17, 20, 20, 8, 6, 12, 21, 13, 2, 13, 15, 22, 11, 17, 19, 0,
5, 14, 3, 7, 11, 2, 15, 18, 5, 16, 12, 3, 8, 8, 3, 2, 24, 14, 23, 6, 23, 2, 1, 4, 6, 13,
9, 17, 6, 12, 20, 23, 16, 9, 10, 21, 11, 14, 3, 1, 2, 9, 21, 21, 7, 19, 4, 13, 10, 6,
15, 19, 0, 9, 23, 10, 6, 1, 2, 2, 18, 20, 16, 19, 10, 4, 9, 19, 14, 7, 10, 9, 16, 1, 16,
8, 16, 4, 3, 9, 11, 23, 5, 19, 4, 14, 20, 2, 7, 22, 5, 4, 7, 5, 1, 23, 4, 23, 23, 21, 1,
19, 15, 8, 22, 11, 1, 14, 13, 17, 20, 1, 8, 18, 7, 22, 3, 14, 0, 12, 14, 10, 5, 3, 1, 13,
8, 15, 13, 18, 1,13, 22, 8, 8, 1, 10, 22, 12, 1, 24, 20, 10, 17, 22, 23, 22, 16, 3, 23,
11, 3, 14, 18, 8, 14, 2, 0, 9, 3, 2, 23, 22, 9, 8, 9, 11, 0, 15, 15, 5, 24, 4, 20, 9, 12,
6, 16, 18, 22, 12, 15, 15, 18, 9, 24, 18, 4, 22, 12, 13, 1, 12, 0, 3, 9, 0, 7, 1, 17, 17,
23, 16, 12, 15, 12, 6, 22, 17, 7, 11, 14, 20, 2, 2, 17, 16, 2, 22, 1, 0, 0, 3, 19, 8, 11,
11, 12, 8, 22, 24, 22, 21, 3, 16, 12, 4, 13, 21, 12, 10, 0, 0, 21, 5, 3, 14, 10, 7, 11, 14,
10, 18, 3, 0, 17, 16, 13, 24, 24, 3, 17, 15, 16, 21, 3, 4, 16, 14, 11, 7, 14, 24, 2, 2, 17, 7}
Returns: 983979105
Don't forget about the mod.
Submissions are judged against all 70 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class RainbowGraph with a public method int countWays(vector<int> color, vector<int> a, vector<int> b) · 70 test cases · 2 s / 256 MB per case