PolygonColors
SRM 406 · 2008-06-18 · by eleusive
SRM 406 · 2008-06-18 · by eleusive · Dynamic Programming, Math
Problem Statement
Problem Statement
Consider a regular polygon with N sides. A diagonal is defined to be a line segment drawn that connects two non-adjacent vertices of the polygon (with the two vertices as its endpoints). A set of diagonals is said to be safe if no two diagonals cross one another, except for possibly at the polygon's vertices.
A coloring of a polygon is a mapping of the non-negative integers, or colors, to the vertices of the polygon. Given a set of safe diagonals, a valid coloring of a polygon is a coloring of the polygon such that no two vertices which are connected by a diagonal or share a side have the same color.
Two diagonals are distinct if at least one of their endpoints is different, and two sets of diagonals are distinct if one set contains some diagonal not contained in the other.
You're given a coloring of a polygon with N sides, where the coloring is given by aint[] colors and N is described by a int . Here, the ith element of colors is the color of the ith vertex. Return how many distinct sets of safe diagonals may be assigned to the polygon such that the coloring is valid. As this result may be very large, return the answer modulo 100000007.
A coloring of a polygon is a mapping of the non-negative integers, or colors, to the vertices of the polygon. Given a set of safe diagonals, a valid coloring of a polygon is a coloring of the polygon such that no two vertices which are connected by a diagonal or share a side have the same color.
Two diagonals are distinct if at least one of their endpoints is different, and two sets of diagonals are distinct if one set contains some diagonal not contained in the other.
You're given a coloring of a polygon with N sides, where the coloring is given by a
Constraints
- N will be between 3 and 50, inclusive.
- colors will have exactly N elements.
- Each element of colors will be between 0 and N-1, inclusive.
Examples
0)
3
{1, 2, 0}
Returns: 1
There are no diagonals we can add to a triangle, so the empty set is the only possibility.
1)
4
{1, 2, 3, 0}
Returns: 3
We can either add 0 or 1 diagonals, and there are two ways to add a diagonal.
2)
4
{0, 1, 0, 1}
Returns: 1
We can't add any diagonals here.
3)
5
{0, 1, 1, 1, 1}
Returns: 0
Here we have vertices that share sides, but have the same color. Even if we choose not to add any diagonals, there are no safe sets here.
4)
4
{0, 0, 0, 1}
Returns: 0
Submissions are judged against all 76 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class PolygonColors with a public method int getWays(int N, vector<int> colors) · 76 test cases · 2 s / 256 MB per case