ThreeColorTrees
SRM 769 · 2019-10-17 · by misof
Problem Statement
Consider the following problem: Given a tree with N vertices, color each of them red, green or blue in such a way that:
- No two red vertices are adjacent.
- No two red vertices share a common neighbor.
(Note that green and blue vertices may be placed arbitrarily.)
Given N, construct any tree with at least 2.62^N valid colorings.
In order to compute the return value, root your tree in any of its vertices and label the vertices 0 through N-1 in such a way that for each vertex x, parent[x] < x. Then, return { parent[1], parent[2], ..., parent[N-1] }.
Notes
- For N = 1, 2, 3, ..., 10 your tree should have at least 3, 7, 18, 48, 124, 324, 848, 2221, 5818, and 15241 valid colorings.
Constraints
- N will be between 1 and 1000, inclusive.
1
Returns: { }
2
Returns: {0 }
The only two-vertex tree has 8 valid colorings. (The only invalid coloring is the one with both vertices red.)
4
Returns: {0, 0, 0 }
A star with four vertices has exactly 48 valid colorings: 2^4 = 16 such that no vertex is red, and 4 * 2^3 = 32 such that one vertex is red.
3
Returns: {0, 1 }
5
Returns: {0, 1, 0, 3 }
6
Returns: {0, 1, 2, 3, 4 }
A path of length 6 has 352 valid colorings.
Submissions are judged against all 110 archived test cases, of which 6 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ThreeColorTrees with a public method vector<int> construct(int N) · 110 test cases · 2 s / 256 MB per case