Editorial for Wesley's Anger Contest 1 Problem 4 (Hard Version) - A Red-Black Tree Problem - Olympiads Online Judge

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)$ $O (N \cdot K^{2})$ dynamic programming solution.

To speed up the solution, we can observe that when computing $merged$ $m e r g e d$ , we only need to consider $dp[v][i][r_i][b_i]$ $d p [v] [i] [r_{i}] [b_{i}]$ and $dp[w][j][r_j][b_j]$ $d p [w] [j] [r_{j}] [b_{j}]$ when $i \le size(v)$ $i \leq s i z e (v)$ and $j \le size(w)$ $j \leq s i z e (w)$ where $size(x)$ $s i z e (x)$ is the size of the subtree of vertex $x$ $x$ .

It can be shown that the resulting time complexity is $\mathcal{O}(N^2)$ $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$ $\sum_{i = 1}^{m} ({s_{i}}^{2}) \leq (\sum_{i = 1}^{m} s_{i})^{2}$ .

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

Comments

There are no comments at the moment.