Editorial for Wesley's Anger Contest 1 Problem 4 - A Red-Black Tree Problem


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: wleung_bvg

Solution Sketch

Subtask 1

We can go through all 2^N subsets of vertices using a bitmask technique and count the number of subsets that have exactly K vertices, and at least 2 red and 2 black vertices, and forms a single connected component, using breadth first search, depth first search, of the union find data structure.

Time Complexity: \mathcal{O}(2^N \cdot N)

Subtask 2

For the second subtask, we can go through all triples of edges and check if it the edges form a single connected component. If it does, then there must be exactly 4 vertices in the connected component. From here, we can check it there are 2 red and 2 black vertices.

Time Complexity: \mathcal{O}(N^3)

Subtask 3

For the third subtask, we will do dynamic programming on a tree. First, we will arbitrarily root the tree at a vertex. For each vertex, we will have dp[v][i][r][b] be the number of subgraphs that are in the subtree of vertex v, that include vertex v, with size i, r red vertices, and b black vertices. A quick time and memory optimization is that we only need to keep track of r, b \le 2. For each vertex, we can go through each of its children and merge the dp arrays. Let w be a child of v. To merge the arrays dp[v] and dp[w], for all tuples (i, r_i, b_i, j, r_j, b_j), we will add the product of dp[v][i][r_i][b_i] and dp[w][j][r_j][b_j] to merged[i + j][\min(2, r_i + r_j)][\min(2, b_i + b_j)]. Remember to mod correctly. The final answer will be the sum of dp[v][K][2][2] for all vertices v\,(1 \le v \le N).

Time Complexity: \mathcal{O}(N \cdot K^2)


Comments

There are no comments at the moment.