Hello Codeforces,

I will present today, and in any day in the future, a means to correctly calculate a corner case of the well known small-to-large trick, and how this can be employed to solve a set of certain problems. This blog is written with encouragement from the Month of Blog Posts initiative.

The standard example.

Let's try to solve the following problem: Cat In a Tree, BOI 2017. Although this problem can be solved employing some greedy algorithm, assume we have no idea what greedy is or how it could be correct, and revert to the basics:

The standard DP.

How can we formulate a DP on this problem? Well, what we need to keep track of is how can we select multiple nodes such that they are all at distance greater than D. When we are considering a correct solution on a subtree and we want to merge it with that of its brother, only one parameter is of importance: the distance of the closest chosen node to the root (As much as any other pair of nodes that traverse their common ancestor would have their length at least as long). And as this seems to be sufficient, we find that the following DP definition is sufficient: $$$dp_{\texttt{node}, \texttt{closest}} = $$$ the highest cardinal of any solution included in the subtree of the node $$$node$$$ such that the closest node chosen is at distance $$$closest$$$

The transition from the sons into their father would look like the following (for two sons $$$s1$$$ and $$$s2$$$): $$$dp_{\texttt{root}, \texttt{min+1}} =\max(dp_{\texttt{s1}, \texttt{min}} + dp_{\texttt{s2}, \texttt{x}},dp_{\texttt{s1},\texttt{x}} + dp_{\texttt{s2}, \texttt{min}})$$$ for any $$$x + min + 2 \ge D$$$ and $$$min \le x$$$

It is clear that the transition for more than two sons is made progressively by merging the current calculated dp in the root with yet another son. Furthermore, we can tweak the definition to represent instead the highest cardinal of any solution whose closest chosen node to the root is at distance at least $$$closest$$$ (i.e. perform suffix maximums). This will help reduce the unnecesary linear traversal of index $$$x$$$, leaving only $$$min$$$ to be iterated.

To sum up these observations in some comprehensive formula, let's rephrase the transition algorithm as follows:

1. At first, we take the $$$dp$$$ array of a son $$$^\dagger$$$. We now assign $$$dp_{\texttt{node}, \texttt{closest+1}} = dp_{\texttt{son}, \texttt{closest}}$$$. We also assign $$$dp_{\texttt{node}, \texttt{0}} = dp_{\texttt{son},\texttt{D-1}} + 1$$$ (i.e. adding a new node to the solution).
2. To further merge this $$$dp$$$ array with that of a different son, we assign: $$$dp_{\texttt{node}, \texttt{T}} = \max( \,(dp_{\texttt{node},\texttt{T}})^{v_1}\,,\,(dp_{\texttt{node}, \texttt{H}} + dp_{\texttt{son}, \texttt{T}})^{v_2}\,,\,(dp_{\texttt{node}, \texttt{T}} + dp_{\texttt{son}, \texttt{H}})^{v_3}\,)$$$ where $$$H$$$ is $$$\max(T, D-T-1)$$$. Then, adjust to preserve the $$$dp$$$ definition by setting $$$dp_{\texttt{node}, \texttt{T}} = \max( dp_{\texttt{node}, \texttt{T}}, dp_{\texttt{node}, \texttt{T+1}})$$$. (Markings $$$v_1, v_2, v_3$$$ are footnotes, not exponents)

Turns out that $$$\dagger$$$ makes this entire algorithm $$$O(N)$$$. $$$\,$$$

So who is this $$$\dagger$$$?

He is the son with the maximum height.

The reasoning for this better analysis than that of the standard small-to-large $$$O(N \cdot log(N))$$$ is the following:

First, we have to do the first transition in constant time. This can be done by keeping the $$$dp$$$ arrays for each node as some sort of deques $$$^1$$$. As such, we can just move the deque into the parent and add an empty entry at the beginning.

Then, observe how it is sufficient to do the second transition within proportional time to the size of the array of the son (i.e. iterating $$$T$$$ from the previously written recurrence within the limit of said size). This clearly makes sense for the correctness of transitions $$$v_1$$$ and $$$v_2$$$, but this also applies to $$$v_3$$$ because:

• if the size of the $$$dp$$$ array of the son we consider spans up to less than $$$\frac{D - 1}{2}$$$, then any other index we would try to update would call values within it that are at least $$$\frac{D - 1}{2}$$$ (as $$$H = \max(T, D - T - 1) \ge \frac{D - 1}{2}$$$). So, $$$H$$$ would always call values out of bounds in $$$v_3$$$, yielding then 0.
• if the size of the updating $$$dp$$$ array is greater than $$$\frac{D - 1}{2}$$$, then beside the now covered and fully considered cases of $$$T \le \frac{D - 1}{2}$$$ (where therefore $$$H = D - T - 1$$$), now remain the cases where $$$H = T$$$. In these, if then $$$T$$$ surpasses the bounds of the array, then the values will always yield $$$0$$$, therefore, both transitions $$$v_2$$$ and $$$v_3$$$ are redundant.

It remain to prove that this sum of sizes of $$$dp$$$-s of not-maximum-in-height sons will yield linear time. For this, I employ the following drawing:

The idea is that everytime we traverse through the second step, we are consuming some sort of potential value, equal to the size of the merged array. This potential increases by one everytime we employ the first step, by extending some succesive maximum height chain. So then, basically everytime we apply the second step, we traverse proportionally as many nodes as the HLD chain (formed by succesively continuing through the tallest descendant) of the son we transition from has.

Furthermore, second type transitions never increase the potential (because the height of the parent remains constant throughout). And then, every node on every chain corresponds to a single possible transition, and as such, every potential increment can only be exhausted once. Therefore, the complexity is $$$O(N - H)$$$, where $$$H$$$ is the unexhausted potential of the chain of the root, as no node on it (and for that matter the root) reports to a second type transition.

And that is the trick, folks.

Discussion on typical patterns

As I've marked in $$$^1$$$ and it kept on appearing, the required data structure for maintaining any sort of such $$$dp$$$ arrays is a deque. There are, however, some problems with that, arising from the fact that the deque allocates a significant amount of memory for a simple instantiation. As such, it has often happened to me that just declaring $$$10^5$$$ of them will be an instant TLE, i.e. a great overhead happening before even running a single line in main.

To reduce the risks of this happening, I suggest the implementation of this trick using a wrapper of a vector instead, similar to the one below, as all the operations we need require insertion from a single end:

template<typename T>
struct Deque {
   vector<T> vec;
   void append_front(T x) { vec.emplace_back(x); }
   T& operator [](const int& x) { return rbegin(vec)[x]; }
   // and other such operations if necessary
};

Furthermore, such a data structure can employ a wide variety of operations, although they need to be generally held on suffixes, as much as one would always update a prefix (and suffix conglomerate values would only need to be updated on said prefix). Along with those, operations that imply lazy modifications on suffixes work as well, usually by pushing them further right whenever accesing a position. Hopefully to illustrate such operations better I leave the following problem:

Final Acknowledgements

I am unaware of a large variety of problems that employ this specific trick. Please let me know in the comments if you know of more interesting applications of it, if you've ever seen any. Here are some others that I do know of:

• Echidistant, Romanian Pre-TST struct a
• Car race, Balkan OI 2023
• CSES Fixed-Length Paths II
• Dominant Indices, thank you greatly estoy-re-sebado for the suggestion!
• Red-Black Tree, 2023 Asia Nanjing Regional and Color the Tree, 2022 Asia Nanjing Regional, the latter illustrating very well an application of lazy propagation on such structures and its power. Thank you bobbilyking for the valuable suggestions!

Also, many thanks towards spatarel for teaching me this trick 3 years ago, and to Andrei_ierdnA & tibinyte for proof-reading.