LADCOMP editorial missing?

Does anybody have an editorial or tutorial for LADCOMP (CodeChef: Practical coding for everyone)?

1 Like

Apparently, the one who should write the analysis is still in the process, so I can give my analysis as the author)

Let d_i be equal to the depth of i of the vertex, and val_i is the depth of the deepest vertex in the subtree of the vertex i, the number of leaves in the tree is cnt. Then, by the definition of the ladder composition, the length of the path leaving the vertex i is val_i - d_i.

Let the lengths of the paths in our ladder composition be l_1 \dots l_k. Then \sum_{i = 1}^{i \leq n} (val_i - d_i) = \sum_{i = 1}^{i \leq k} l_i \cdot (l_i + 1) / 2 \iff 2 \sum_{i = 1}^{i \leq n} (val_t - d_i) = \sum_{i = 1}^{i \leq k} l_i^2 + \sum_{i = 1}^{i \leq k} l_i. And the latter is equal to n-cnt

Thus, you need to be able to maintain the sum \sum_{i = 1}^{i \leq k} (val_t - d_i)

It is clear that when we get a vertex, the maximum depth changes only on the prefix of vertices, so we can make bin ascents + UP to to check the maximum depth. The asymptotics of the solution is O (n \cdot log^2)

Let’s solve it more optimally. Let the new vertex be v, A_i - all vertices at the depth of i. Then we note that if there is an old vertex in the subtree of the vertex u at the depth of d_v, then its answer will not change. So we are only interested in vertices of the form lca (v, {A_{d_v}}_j). And among them, you need to take a vertex with a minimum depth, which is not difficult to do with a set with pre-calculated entry times for the vertices.

Solve #include <iostream>#include <vector>#include <set>using namespace std; - Pastebin.com

2 Likes