Connection Status:
Competition Arena > CycleColoring

CycleColoring

SRM 614 · 2013-12-22 · by Cricicle

SRM 614 · 2013-12-22 · by Cricicle · Dynamic Programming, Graph Theory, Math
Class Name: CycleColoring
Return Type: int
Method Name: countColorings
Arg Types: (vector<int>, vector<int>, vector<int>, int)
Problem Statement

Problem Statement

This problem statement contains superscripts and/or subscripts. It may not display properly outside the applet.


Today, Bob is trying to count the colorings of a strange graph. It looks like a cycle of cycles.


The graph has two types of edges -- solid edges and dashed edges.


The edges between the vertices of the original cycles are all solid edges.
The edges that connect cycles together are all dashed edges.


More precisely, the graph consists of N cycles. The cycles are labelled, in order, as C0, C1, ..., CN-1. You are given a int[] vertexCount with N elements. Cycle Ci has vertexCount[i] vertices. The vertices of cycle Ci are labelled, in order, as vi, 0, vi, 1, ..., vi, vertexCount[i]-1. Note that the last vertex in this order is also connected to the first one. All of the edges that form these cycles are solid edges.


You are also given two int[]s fromVertex and toVertex, with N elements each. These int[]s describe the connection between cycle Ci and Ci+1 as follows: The vertex in cycle Ci with label vi, fromVertex[i] and the vertex in cycle Ci+1 with label vi+1, toVertex[i] will be connected with a dashed edge.


Bob has K distinct colors. He wants to know how many different ways there are to color the vertices of the graph under the following two rules:

  • Vertices connected with a solid edge must be colored using a different color.
  • Vertices connected with a dashed edge must be colored using the same color.

Two colorings are considered different if there is a vertex vi, j which has a different color in each coloring. Let C be the number of colorings that correspond to the given rules. As C can be extremely large, you should compute and return the value (C modulo 1,000,000,007).

Notes

  • i+1 is considered modulo N - hence, references to cycle CN are referring to cycle C0.

Constraints

  • vertexCount will contain between 1 and 50 elements, inclusive.
  • vertexCount, fromVertex, and toVertex will all contain the same number of elements.
  • Each element of vertexCount will be between 3 and 1,000,000, inclusive.
  • Element fromVertex[i] will be between 0 and vertexCount[i] - 1, inclusive.
  • Element toVertex[i] will be between 0 and vertexCount[i+1] - 1, inclusive.
  • K will be between 2 and 1,000,000,000, inclusive.
Examples
0)
{3, 3}
{0, 0}
{0, 0}
3
Returns: 12

This graph consists of two cycles of length 3. There are two dashed edges, each connecting vertex 0 of one cycle to vertex 0 of the other cycle. These two vertices must share the same color. We have 3 possibilities for that color. Once we fix it, we have 2 possibilities how to color the rest of each cycle. Hence, the answer is 3*2*2 = 12.

1)
{6}
{4}
{1}
3
Returns: 12

This graph only has one cycle. Note that for N=1 there is still one dashed edge and it connects two vertices on the same cycle. The 12 valid colorings of the resulting graph correspond to the 12 valid colorings of the graph from Example 0.

2)
{3, 3}
{0, 1}
{1, 2}
3
Returns: 0

Vertices 0 and 2 on cycle 0 must both have the same color as vertex 1 on cycle 1. However, vertices 0 and 2 on cycle 0 are adjacent and therefore must have different colors. This is a contradiction. Therefore, there are no valid colorings of this graph.

3)
{9, 5}
{8, 3}
{0, 2}
8
Returns: 589124602
4)
{14, 15, 16, 17}
{5, 10, 4, 6}
{10, 3, 14, 10}
614
Returns: 818050159

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

Coding Area

Language: C++17 · define a public class CycleColoring with a public method int countColorings(vector<int> vertexCount, vector<int> fromVertex, vector<int> toVertex, int K) · 202 test cases · 2 s / 256 MB per case

Submitting as anonymous