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

To speed up the solution, we can observe that when computing $merged$ ~merged~, we only need to consider $dp[v][i][r_i][b_i]$ ~dp[v][i][r_i][b_i]~ and $dp[w][j][r_j][b_j]$ ~dp[w][j][r_j][b_j]~ when $i \le size(v)$ ~i \le size(v)~ and $j \le size(w)$ ~j \le size(w)~ where $size(x)$ ~size(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)$ ~\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)$ ~\mathcal{O}(N^2)~

Comments

There are no comments at the moment.