Editorial for Wesley's Anger Contest 1 Problem 4 (Hard Version) - 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.

Author: wleung_bvg

Please refer to the original problem's editorial for the \mathcal{O}(N \cdot K^2) dynamic programming solution.

To speed up the solution, we can observe that when computing merged, we only need to consider dp[v][i][r_i][b_i] and dp[w][j][r_j][b_j] when i \le size(v) and j \le size(w) where size(x) is the size of the subtree of vertex x.

It can be shown that the resulting time complexity is \mathcal{O}(N^2). Proof is left as an exercise to the reader. Hint: \sum_{i = 1}^m ({s_i}^2) \le (\sum_{i = 1}^m s_i)^2.

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


There are no comments at the moment.