Introduction

Most of DP algorithms I studied online, there are some subtleties that I didn't find any proof of. May be they are found somewhere already, but not to my knowledge.

I think most people find the things that I'm going to prove here intuitive and need no proof, but for if you're really picky about being uncertain of something if you didn't see a proof (like me), it can bother you. Also, knowing the proofs can sometimes better help the thinking process.

The purpose of this blog is to provide examples of proofs of famous DP algorithms to, first show them, and second serve as a general pattern of techniques on how would one prove a DP algorithm.

Now, most DP problem involve a set of states $$$V$$$, and a set of transitions $$$E$$$ such that $$$(V, E)$$$ constitutes a directed acyclic graph or DAG (sometimes weighted).

Thus, we will continue discussing DP calculations on a DAG.

Conventions

• A graph $$$G = (V, E)$$$ is a pair of sets $$$V$$$ and $$$E$$$ where $$$E \subseteq V^2$$$. In this blog, we will assume $$$(u, u) \notin E$$$ for all $$$u \in V$$$.

• For $$$u \in V$$$, we define $$$N(u) = \{ v : (u, v) \in E \}$$$

• A path is a sequence $$$(a_1, a_2, \dots, a_k)$$$ of pairwise distinct vertices where $$$(a_i, a_{i + 1}) \in E$$$ for all $$$1 \leq i \lt k$$$.

• For a path $$$p = (a_1, a_2, \dots, a_k)$$$, we say $$$v \in p$$$ if $$$a_i = v$$$ for some $$$1 \leq i \leq k$$$, and we say that an edge $$$(u, v) \in p$$$ if $$$a_i = u$$$ and $$$a_{i + 1} = v$$$ for some $$$1 \leq i \lt k$$$.

• The notation $$$\mathbf{1}[\text{condition}]$$$ denotes a predicate that is $$$1$$$ when the condition is true and $$$0$$$ otherwise.

Warmup: Counting DP

Fix $$$S \subseteq V$$$, and let $$$P_u$$$ be the set of all paths starting at $$$u$$$ and ending at $$$s \in S$$$.

Define $$$D_u = |P_u|$$$. We want to show the following recursive formula for all $$$u \in V$$$

• if there doesn't exist a path from $$$u$$$ to $$$s \in S$$$, then $$$D_u = 0$$$, (which is trivially correct since $$$P_u = \emptyset$$$)

• otherwise $$$\displaystyle D_u = \sum_{v \in N(u)} D_v + \mathbf{1}[u \in S]$$$.

If so, we can compute $$$D$$$ using the following algorithm (or you can also use recursion)

1. Initialize $$$D$$$ to $$$0$$$ s.
2. Initialize $$$D_s = 1$$$ for all $$$s \in S$$$.
3. Let $$$L$$$ be a topological order of $$$G$$$ in reverse.
4. For each $$$u \in L$$$,
   • For each $$$v \in N(u)$$$:
   • $$$D_u := D_u +D_v$$$.

The correctness of such an algorithm can be just the recursive formula an induction on the order in the topological sorting.

Define $$$P_{u, v}$$$ for $$$(u, v) \in E$$$ denote the set of all paths from $$$u$$$ to $$$s \in S$$$ that starts with $$$u$$$ and $$$v$$$, and define

Then, clearly

Moreover, when $$$v, v' \in N(u)$$$ have $$$v \neq v'$$$, $$$P_{u, v}$$$ and $$$P_{u, v'}$$$ are disjoint, and clearly $$$S_u$$$ and $$$P_{u, v}$$$ are disjoint.

Thus,

It remains to see that $$$|P_{u, v}| = |P_v|$$$, by showing that the map $$$(u, v, \dots, s) \mapsto (v, \dots, s)$$$ is a bijection between $$$P_{u, v}$$$ and $$$P_v$$$ (which is left as an exercise), and the conclusion follows.

This can serve as a template for most DP counting problems.

D = [0, 0, ..., 0] (n times)
D[0] = 1
for u in [1, n]:
  for i in [1, min(u, 6)]:
    D[u] += D[u - i]

More advanced counting

Weigh the edges of $$$G$$$ with a weight function $$$w : E \to \mathbb{R}$$$, and define $$$D_u$$$ and $$$S$$$ as before.

For a path $$$p = (a_1, a_2, \dots, a_k)$$$, define its weight as

Also, define

That is, $$$F_u$$$ sums the weights of edges over all paths from $$$u$$$ to an $$$s \in S$$$ (convention is that empty sum is $$$0$$$ and empty product is $$$1$$$).

We want to show that we can calculate $$$F$$$ this way:

• If there doesn't exist a path of at least one edge from $$$u$$$ to an $$$s \in S$$$, then $$$F_u = 0$$$.

• Otherwise,

Thus, we can compute it this way

1. Initialize $$$F$$$ to $$$0$$$ s.
2. Let $$$L$$$ be a topological order of $$$G$$$ in reverse.
3. For each $$$u \in L$$$,
   • For each $$$v \in N(u)$$$:
   • $$$F_u := F_u + w(u, v) D_v + F_v$$$.

Assume otherwise. Then,

as desired.

Knapsack DP

Redefine $$$F$$$ as follows: for any $$$u$$$ where $$$P_u \neq \emptyset$$$ (if $$$P_u = \emptyset$$$, define $$$F_u = -\infty$$$),

In other words, $$$F_u$$$ is the maximum sum of weights over all paths from $$$u$$$ to $$$s$$$.

(Note that the empty path from $$$s$$$ to $$$s$$$ has weight $$$0$$$, and so $$$F_s = 0$$$).

We want to show that

Thus, we compute $$$F$$$ this way

1. Initialize $$$F_u$$$ to $$$-\infty$$$ for all $$$u \in V$$$
2. Set $$$F_s = 0$$$ for all $$$s \in S$$$.
3. Let $$$L$$$ be a topological order of $$$G$$$ in reverse.
4. For each $$$u \in L$$$,
   • For each $$$v \in N(u)$$$:
   • $$$F_u := \max(F_u, w(u, v) + F_v)$$$.

We can show it this way:

Everything else is the same when we're doing $$$\min$$$ instead of $$$\max$$$ (switching $$$-\infty$$$ to $$$\infty$$$).

Exercise. build the implicit DAG for the actual knapsack problem. Show that the maximum weight of a path on such a DAG is actually what the problem requires.

Expected Value DP

Keep the definitions as they are, and keep the weight function $$$w$$$, however, here, for simplicity, we consider $$$S = \{ s \in V : N(s) = \emptyset \}$$$.

Define a probability distribution $$$\Pr$$$ on each neighbourhood of a vertex.

In other words, $$$\Pr : E \to \mathbb{R}_{\geq 0}$$$ is a function that satisfies the following constraint

• for any $$$u \in V$$$, where $$$N(u) \neq \emptyset$$$,

We want to solve the following classical problem:

1. Start at a node $$$u$$$
2. Choose $$$v \in N(u)$$$ with probability $$$w(u, v)$$$.
3. Walk through the edge $$$(u, v)$$$, i.e. set $$$u := v$$$.
4. Terminate if $$$u \in S$$$, otherwise go to step 2.

We want the expected sum of weights of edges.

To state that problem formally, we can define for any path $$$p$$$

In other words, if we let $$$F_u = 0$$$ when $$$u \in S$$$, and when $$$u \notin S$$$, we have

we want to calculate $$$F$$$. We can do that by showing that for all $$$u \in V$$$,

So, that we can compute $$$F$$$ as follows

1. Initialize $$$F_u$$$ to $$$0$$$ for all $$$u \in V$$$
2. Let $$$L$$$ be a topological order of $$$G$$$ in reverse.
3. For each $$$u \in L$$$, if $$$u \notin S$$$:
   • For each $$$v \in N(u)$$$:
   • $$$F_u := F_u + \Pr[u, v] (w(u, v) + F_v)$$$.

To proceed with the proof, we need to prove the following lemma.

Lemma 1. For any $$$u \in V$$$,

Proof. We can define $$$G_u = 1$$$ when $$$N(u) = \emptyset$$$, and otherwise

We have

Thus, the above equations represent a system of equations that has a unique solution $$$G_u = 1$$$ for all $$$u \in V$$$ (the rank of the matrix is clearly $$$|V|$$$ if we order the nodes by topological sorting).

Now, I think you know where I'm going with this:

(Note: if we want the expected sum of values of an array $$$a_u$$$, we can define $$$F_u = a_u$$$ when $$$N(u) = \emptyset$$$ and replace $$$w(u, v)$$$ with $$$a_u$$$).

Abstract Operations

We can replicate the knapsack DP arguments for abstract operations.

Let $$$\otimes$$$ and $$$\odot$$$ be commutative and associative operations over a set $$$R$$$ where for any $$$a, b, c \in R$$$, we have

You can think of $$$\otimes$$$ as the multiplication $$$\times$$$, and $$$\odot$$$ as addition $$$+$$$.

Moreover, let $$$0_\odot \in R$$$ be the identity of the operation $$$\odot$$$ (similar for $$$0$$$ for addition) and $$$1_\otimes$$$ is the identity of the operation $$$\otimes$$$ (similar for $$$1$$$ for multiplication).

In other words, for all $$$a \in R$$$

• $$$0_\odot \odot a = a$$$, and

• $$$1_\otimes \otimes a = a$$$.

We also require the additional assumption that for all $$$a \in R$$$,

(In formal terms, $$$(R, \odot, \otimes)$$$ is a commutative semiring).

Now, suppose we redefine the weight function $$$w$$$ so that $$$w : E \to R$$$. Moreover, for any path $$$p$$$, we can define

Fix $$$S \subseteq V$$$ (as usual). Let $$$P_u$$$ denote all paths starting from $$$u$$$ to a node $$$s \in S$$$. We want to find for each $$$u \in V$$$

Let $$$T_u = 1_\otimes$$$ if $$$u \in S$$$ and $$$0_\odot$$$ otherwise.

We claim that

and so we can use the following algorithm to compute $$$F$$$:

1. Initialize $$$F$$$ to $$$0_\odot$$$.
2. For each $$$s \in S$$$, set $$$F_s := 1_\otimes$$$.
3. Let $$$L$$$ be a topological sorting of $$$V$$$ in reverse order.
4. For each $$$u \in L$$$:
   • For each $$$v \in N(u)$$$:
     • $$$F_u = F_u \odot (w(u,v) \otimes F_v)$$$.

We can prove the recursive formula in exactly the same way: for $$$u \notin S$$$,

Exercies:

Problem 1. given a weighted graph with $$$n \leq 20$$$ vertices, and a source node $$$s$$$, with weights $$$0 \leq w(u, v) \lt 10^9 + 7$$$ for $$$(u, v) \in E$$$.

Let $$$P$$$ be the set of all hamiltonian paths starting from $$$s$$$, and let $$$w(p)$$$ be the product of weights over all edges on the path $$$p$$$.

Find

modulo $$$10^9 + 7$$$.

Problem 2. given positive integers $$$N, M \leq 10^3$$$, and an array of positive integers $$$a_1, a_2, \dots, a_N \leq 10^9$$$.
Let $$$\mathcal{S}$$$ be the set of all subsets of $$$S \subseteq \{ 1, 2, \dots, N \}$$$ where

is divisible by $$$M$$$.

Moreover, for any subset $$$S \in \mathcal{S}$$$, define $$$A(S)$$$ to be the bitwise AND of all $$$a_i$$$ for $$$i \in S$$$.

Find

This blog discusses potential solutions to this problem.

It's a famous technique and all you can find online is this comment on a blog discussing the problem.

I tried hard to understand it by drawing a tree and following up with how it works, but it seemed a bit confusing to me (probably a skill issue), and this idea was all the resources I found online on the trick.

Also, what about if there are variants (e.g. maximum sum of values with weight exactly $$$W$$$ instead of at most)?

There comes a brilliant idea by my friend IsaacMoris. It goes as follows:

1. Do classical Euler tour indexing (or tree flattening) to obtain three arrays $$$\text{tin}$$$, $$$\text{tout}$$$, $$$\text{vertex}$$$, where $$$\text{vertex}$$$ is defined as $$$\text{vertex}[\text{tin}[i]] = i$$$ for all $$$0 \le i \lt n$$$, and so the subtree of the vertex $$$v$$$ is the subarray $$$[l, r]$$$ in $$$\text{vertex}$$$ where $$$l = \text{tin}[v]$$$ and $$$r = \text{tout}[v] - 1$$$.

2. Do take or leave DP on the $$$\text{vertex}$$$ array as follows: either

• take the current item and go to the next element in the vertex array (corresponding to a vertex in the subtree of the current node), so dp[i][j] = dp[i + 1][j - weight[vertex[i]] + value[vertex[i]], or

• leave the current item and so skip the entire subtree. In other words, do the transition dp[i][j] = max(dp[i][j], dp[tout[vertex[i]]][j])

That's really it. This is my accepted submission based on this idea!

Prescript

This is a beginner concept that I think many people know but I haven't seen written explicitly anywhere, and I have explained it before multiple times to many people asking me "where can I learn more about bitmasks and bitwise operations?"

I haven't seen this explained anywhere so that I can refer them to this resource. Hence, I'm writing about it myself. The techniques in this blog are very intuitive and simple to the extent that you can wonder "why are we even talking about this?" But I do often find it very useful to state something explicitly (and formally), because sometimes intuition can be misleading if not held accountable and made explicit.

Throughout the blog, I try to make the concepts as easy to read as possible while also not eliminating formality. So, I keep the more formal writings enclosed inside spoiler blocks

which you can feel free to skip if uncomfortable with formality, and you'd still benefit from the blog. However, they are highly recommended as they can enhance the understanding of the concept.

Prerequisites: naive/basic set theory

Introduction

If you have taken a discrete math course, you probably saw this argument (noting that $$$\mathcal{P}(S)$$$ is the power set of $$$S$$$):

Given a finite set $$$S$$$ where $$$|S| = n$$$ for some non-negative integer $$$n$$$, then $$$|\mathcal{P}(S)| = 2^n$$$. To see this, $$$S = \{ s_1, s_2, \dots, s_n \}$$$ and you associate to every subset $$$H \subseteq S$$$ a binary string $$$x_1 x_2 \dots x_n$$$ where $$$x_i = 1$$$ if and only if $$$s_i \in H$$$ and $$$0$$$ otherwise. Since there are $$$2^n$$$ such strings (each bit has two options $$$0$$$ and $$$1$$$), we have our conclusion.

This "association" is insightful.

It is also very intuitive: you can tell everything about a subset of a set by identifying which elements are in the subset and which elements are not.

The reverse is also true: you can tell everything about a bitmask by identifying which bits are on and which bits are off!

To that end, let's associate with every non-negative integer $$$x$$$ a set $$$\varphi(x)$$$ containing all positions that are 1 in its binary representation. For example,

• $$$\varphi(0) = \emptyset$$$

• $$$\varphi(1) = \{ 0 \}$$$

• $$$\varphi(2) = \{ 1 \}$$$

• $$$\varphi(3) = \{ 0, 1 \}$$$

• $$$\varphi(4) = \{ 2 \}$$$

• $$$\varphi(5) = \{ 0, 2 \}$$$

and so on. Moreover, observe that such a map $$$\varphi$$$ is invertible, with $$$\displaystyle \varphi^{-1}(S) = \sum_{i \in S} 2^i $$$.

Now, why is this association insightful? There are three applications which I think this association makes the understanding of bitmasks much easier:

1. Properties of bitwise operations

2. Submasks and supermasks and brute force over subsets

Disclaimer: it's not useful to think about ALL bitwise problems in this way. For example, the techniques in this blog are irrelevant to a problem like this.

Properties of bitwise operations

A very nice thing about the map $$$\varphi$$$ is that it behaves nicely with bitwise operations. In particular, for any two non-negative integers $$$x, y$$$, we have

1. $$$\displaystyle \varphi(x \, \& \, y) = \varphi(x) \cap \varphi(y)$$$ (bitwise AND is just the intersection of the sets)

2. $$$\varphi(x \, |\, y) = \varphi(x) \cup \varphi(y)$$$ (bitwise OR is just the union of the sets)

3. $$$\varphi(x \oplus y) = \varphi(x) \Delta \varphi(y)$$$ (the bitwise XOR is the symmetric difference between the sets)

You also may have observed before that there is a back-and-forth going between the word and and the intersection of two sets, and the word or and the union of two sets. Even in the definition of union and intersection, you see that

• $$$A \cup B = \{ x : x \in A \textbf{ or } x \in B \}$$$

• $$$A \cap B = \{ x : x \in A \textbf{ and } x \in B \}$$$

Even we see that in logic, there is an intuition of similarity between $$$\lor$$$ and $$$\cup$$$ and $$$\land$$$ and $$$\cap$$$, and $$$p \lor (q \land r) = (p \lor q) \land (p \lor r)$$$ while in sets, $$$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$$$ and even De Morgan's Laws on logic transfer to sets.

Since we're working with all finite sets, the above interchange between bitmasks and sets is basically how we express this intuitive notion of similarity between $$$\lor$$$ and $$$\cup$$$ and $$$\land$$$ and $$$\cap$$$.

In other words, this says that bitmasks and bitwise operations behave exactly like sets with $$$\cap, \cup, \Delta$$$.

Now, this is particularly useful since showing properties about bitwise operations is equivalent to showing properties about sets, and dealing with sets can be easier.

Example 1. (Warmup) For any non-negative integers $$$x, y, z$$$, $$$x \& (y \oplus z) = (x \& y) \oplus (x \& z)$$$

In this example, every bit behaves independently of one another, and so it's easy to try to verify it for just $$$x, y, z \in \{ 0, 1 \}$$$ and generalize.

However, using sets, showing that for any finite sets $$$X, Y, Z$$$ we have $$$X \cap (Y \Delta Z) = (X \cap Y) \Delta (X \cap Z)$$$ is sufficient.

Now, while showing the set theoretic identity mathematically is a bit more complicated version of the $$$x, y, z \in \{0, 1\}$$$ argument, visualizing it on a venn diagram can make it too much easier:

If $$$X$$$ is red, $$$Y$$$ is yellow, and $$$Z$$$ is blue, then $$$Y \Delta Z$$$ makes regions $$$2, 3, 4, 5$$$, and so $$$X \cap (Y \Delta Z)$$$ makes regions $$$4, 5$$$. On the other hand, $$$X \cap Y$$$ makes $$$4, 7$$$ and $$$X \cap Z$$$ is $$$5, 7$$$, and so $$$(X \cap Y) \Delta (X \cap Z)$$$ makes $$$4, 5$$$ as well.

Two take-aways:

1. The idea of using a venn diagram to verify an identity related to bitmasks is very useful and can actually be used to verify many other identities about bitmasks, as will be shown in the examples below.

2. To show an identity in bitmasks, it is sufficient to show the analog identity in sets. (Formally, you can apply $$$\varphi$$$ on the identity and convert the proper operations to obtain the analog identity in sets).

Example 2: for any non-negative integers $$$x, y$$$, if $$$x \& y = 0$$$, then $$$x | y = x + y$$$

Now, this is tricky, since we don't know how $$$\varphi$$$ behaves with addition yet. But, we can still do something:

Let $$$X = \varphi(x), Y = \varphi(y)$$$, and name $$$\gamma = \varphi^{-1}$$$. Then, the identity above says that if $$$X \cap Y = \emptyset$$$ (or $$$X$$$ and $$$Y$$$ are disjoint, have no elements in common), then

This basically says that $$$\displaystyle \sum_{i \in (X \cup Y)} 2^i = \sum_{i \in X} 2^i + \sum_{i \in Y} 2^i$$$, which is clear when $$$X \cup Y$$$ are disjoint. (If we want to be super-formal, then we can use induction)

Exercise: show that when $$$(x \& y) = x$$$, then $$$y = x + (y \oplus x)$$$. (Hint: show that $$$x | (y \oplus x) = y$$$ and use what we've just shown)

Example 2: for any non-negative integers $$$x, y$$$, $$$(x | y) = x + y - (x \& y)$$$

If we apply the same technique as above, we get

Looks familiar? Yes, this is nothing but the inclusion/exclusion principle. Intuitively, this looks very clear from the venn diagram above, if you take blue and green, then we repeat $$$7$$$ and $$$6$$$ when adding $$$x + y$$$ and so we just remove the overcounted part $$$7$$$ and $$$6$$$.

Exercise: show that for any non-negative integers $$$x, y, z$$$, $$$(x | y | z) = x + y + z - (x \& y) - (x \& z) - (y \& z) + (x \& y \& z)$$$.

Example 3: for any non-negative integers $$$x, y$$$, $$$x \oplus y = x + y - 2(x \& y)$$$

This has been labelled before as a weird property in some blogs that I have seen, and hasn't been straightforward for many people I have spoken with. However, it can be seen clearly now, since it can be seen clearly from the venn diagram that $$$(x \oplus y) + (x \& y) = (x | y)$$$

So, manipulating the above equation by adding $$$x \& y$$$ to both sides yields $$$x | y = x + y - (x \& y)$$$ which is inclusion/exclusion shown in the previous example.

You can even observe the identity directly (without any manipulations) through a venn diagram, which goes to show how useful this can be.

Exercise: show that $$$x + y + z = (x \oplus y \oplus z) + 2(x \& y) + 2(x \& z) + 2(y \& z) - 4(x \& y \& z)$$$

Additional Exercises: show all the bitwise formulas in this blog

Submasks and supermasks and subset search

The definitions of submasks/supermasks vary, $$$x$$$ is a submask of $$$y$$$ (or $$$y$$$ is a supermask of $$$x$$$) if

1. $$$(x \& y) = x$$$
2. $$$(x | y) = y$$$
3. All the bits lid in $$$x$$$ are lid in $$$y$$$.

In sets, it's simple: if $$$X = \varphi(x)$$$ and $$$Y = \varphi(y)$$$, then $$$x$$$ is a submask of $$$y$$$ if and only if $$$X \subseteq Y$$$. Convenient, right?

Of course, this is the same as $$$X \cap Y = X$$$ and $$$X \cup Y = Y$$$.

Now, this means that if $$$(x \& y) = z$$$, then $$$z$$$ is a submask of both $$$x$$$ and $$$y$$$, and if $$$(x | y) = z$$$, then both $$$x$$$ and $$$y$$$ are submasks of $$$z$$$.

Note: observe that the number of possible submasks is $$$2^{|\varphi(x)|}$$$, which is analogous to the number of elements in the powerset of a set. $$$|\varphi(x)|$$$ can be calculated using __builtin_popcount

An example problem where thinking in terms of submasks/subsets is this.

Solution: Observe that if $$$a$$$ is a submask of $$$b$$$, then we're done since $$$A \cup B = B$$$. Moreover, once we apply the third operation, then we know $$$b$$$ becomes a submask of $$$a$$$ and $$$b \le a$$$, and so we can only apply the second operation since the other operations only increase $$$a$$$ but not decrease it.

Additionally, if we increase apply the third operation to get $$$x = (a | b)$$$ and then increase $$$b$$$ to $$$x$$$, this is the same as increasing $$$b$$$ until it becomes $$$x$$$ and then applying $$$a = (a | b)$$$. So, it's optimal to apply it in the end, since you can get to a supermask $$$b'$$$ of $$$a$$$ that is less than $$$x$$$ currently. So, what you do is either apply first or second operation then at the end apply third if necessary.

Then, we're trying to find $$$x, y$$$ such that $$$(a + x) \subseteq (b + y)$$$ and $$$x + y$$$ is minimal. It is sufficient to loop over $$$y$$$, and find the smallest submask of $$$b + y$$$, $$$a'$$$ that is at least $$$a$$$, and set $$$x = a' - a$$$. This is easy to do by iterating over bits of $$$b + y$$$ from largest to smallest.

Subset search: We previously said every subset of a certain set can be mapped into a bitmask as well.

This means that if we have an array of $$$n \leqslant 20$$$ elements, then we can brute force the subsets of the set $$$\{ 0, 1, 2, \dots, n - 1\}$$$ its $$$2^n$$$ subsets by just iterating over all the bitmasks of size $$$2^n$$$, which is a well-known technique.

If we have a subset $$$X$$$, then checking that $$$j \in X$$$ is equivalent to checking that $$$\{ j \} \cap X = \{ j \}$$$, or $$$\gamma(\{ j \}) \& \gamma(X) = \gamma(\{ j \})$$$ which is the same as $$$2^j \& x = 2^j$$$. That's why we often see the condition if ((1 << j) & x), which is actually saying if (((1 << j) & x) == (1 << j)).

Update: check comments for additional content :)

Can you spot any difference between $$$max$$$ and $$$\text{max}$$$ or $$$dp$$$ and $$$\text{dp}$$$?

How about $$$\lfloor \frac{max(a, b, c)}{b} \rfloor$$$ and $$$\left \lfloor \frac{\max(a, b, c)}{b} \right \rfloor$$$? Or even $$$\displaystyle \left \lfloor \frac{\max(a, b, c)}{b} \right \rfloor$$$!

While appreciating the efforts and the careful elaborate writing of the authors, I have faced many issues with latex writing in editorials that have frustrated me while reading over the years, so I thought of writing this blog to settle many of such issues and making our equations in editorials the prettiest possible.

I'm going to use this editorial in problem F div 1 an example and refer to it in things that can be improved. Of course, that doesn't mean any offence to satyam343's beautiful and careful writing of the editorial nor his/her LaTeX writing/skills, he/she has done it beautifully.

Also, note that any code that is quoted in this blog like this will be assumed to be enclosed between two dollar signs to represent LaTeX writing.

Tip 1. No italic writings in LaTeX

If we look at hint 1 in the editorial, we can see the author wrote $$$frequency[0]$$$ by just writing frequency[0]. The way I would recommend writing something like this is to use the command \text{your text} which makes a huge difference.

If you write it as \text{frequency}[0], it will appear as $$$\text{frequency}[0]$$$. More pretty, right?

You can even notice the difference if we made it as a block equation of sums (with two dollar signs)

instead of

Another example is when editorials are explaining a DP solution, they write $$$dp(i, j, k)$$$ or $$$DP(i, j, k)$$$ or $$$dp[i][j][k]$$$. One example is the same referenced editorial writes $$$dp[l][suff\_sum]$$$ as dp[l][suff\\_sum]

The way I recommend writing this is \text{dp}[l][\text{suff}\\_\text{sum}] which renders as $$$\text{dp}[l][\text{suff}\_\text{sum}]$$$, a big difference! In a similar manner, you can also write $$$\text{dp}(i, j, k)$$$ or $$$\text{DP}(i, j, k)$$$. I prefer $$$\text{dp}[i][j][k]$$$ using square brackets and a non-italic "dp."

You can see this can change $$$d = suff\_sum + initial\_cur\_sum$$$ to $$$d = \text{suff}\_\text{sum} + \text{initial}\_\text{cur}\_\text{sum}$$$. If it's annoying to write \text every time, just copy it and polish the whole text with it once in the end.

Of course, the standard is that up to preference, I recommend not using \text for one letter variables, like $$$x, y, z, a, b, c, l$$$ (we can see they would look like this $$$\text{x}, \text{y}, \text{z}, \text{a}, \text{b}, \text{c}, \text{l}$$$). However, two letters or more, \text makes it more clear and readable.

One final note in this regard: some functions in LaTeX are special and only need \ and no text like $$$\max, \min$$$, and $$$\gcd$$$. I wrote this like \max, \min, \gcd and not using \text. You can see $$$\max(a, b, c)$$$ is way better than $$$max(a, b, c)$$$ same with $$$\gcd(a, b, c)$$$ and $$$gcd(a, b, c)$$$.

Tip 2. Enclosing brackets

This is to change

to

There were differences explained in the previous tip, but this tip focuses on the parenthesis.

The first was rendered using the code is

dp[i][new\_suffix\_max]  = \max(dp[i][new\_suffix\_max], \min\limits_{k = p-1}^{i} best[k] + cost)

and the second was using

\text{dp}[i][\text{new}\_\text{suffix}\_\text{max}] = \max\left(\text{dp}[i][\text{new}\_\text{suffix}\_\text{max}], \min\limits_{k = p-1}^{i} \text{best}[k] + \text{cost}\right)

The major change I want to highlight is \left( and right) to enclose the parenthesis. This is when your parenthesis include some fraction, summation, minimum/maximum with limits, integration, exponentation, ...etc. The parenthesis or brackets are enlarged to enclose your expression.

Let's have some examples for comparison:

• $$$dp[x] = dp[\frac{max(x + 1, 1)}{2}] + 1$$$ vs $$$\text{dp}[x] = \text{dp}\left[\frac{\max(x + 1, 1)}{2}\right] + 1$$$.

• $$$\lfloor \frac{\max(0, 1 - d)}{2} \rfloor$$$ vs $$$\left\lfloor \frac{\max(0, 1 - d)}{2} \right\rfloor$$$

• Consider the difference between $$$\displaystyle gcd(x + \sum_{i = 1}^n a_i + y, z)$$$ and $$$\displaystyle \gcd\left(x + \sum_{i = 1}^n a_i + y, z\right)$$$. The parenthesis were enlarged to enclose the summation inside.

Final random tips for LaTeX and editorials in general

• Use block equations. When you feel like your equation is a bit too big, use two dollar signs instead of one to enclose your equation. That makes them block in one separate line instead of inline. It's OK that it makes the editorial bigger; readability beats size.

• Separate your paragraphs with new lines whenever it becomes crowded. Worry less about that the editorial becoming too big than it being cramped and unclear. Seek clarity.

• Use \dots.

• Use \displaystyle

• Use \cdot to denote a product, not *.

• Use subscripts if needed.

• Please, in problems like this, don't put names inside dollar signs to highlight. Use bold text. Write " Abdullah and Kifah " using **Abdullah** and **Kifah**, don't write "$$$Abdullah$$$ and $$$Kifah$$$" using $$$Abdullah$$$ and $$$Kifah$$$. If for some reason you insist on using dollar signs, use \text and display it as $$$\text{Abdullah}$$$ and $$$\text{Kifah}$$$

• Never leave a variable without dollar signs. Don't say "an array of n elements", say "an array of $$$n$$$ elements".

Finally, if anyone has any other tips that I can add, please don't hesitate to share with us in the comments.

Introduction

This blog contains well-known facts and techniques about Harmonic Numbers that are scattered all over editorials of some problems, comments, and some parts of blog posts. The place where I found most of the facts explained here is the brilliant blog by Nisiyama_Suzune about Möbius inversion. However, for the untrained eye, this blog may seem as if it's investigating something advanced and the facts explained inside will be missed. Moreover, there were some omitted proofs, so I thought it would be nice to collect all these facts/techniques in one place and add their proofs in (hopefully) an understandable but precise style, which would be useful for many.

For starters, the $$$n$$$th harmonic number, $$$H_n$$$, is the sequence $$$\displaystyle H_n = \sum_{i = 1}^{n}\frac{1}{i}$$$. We will investigate two techniques related to this sequence.

1. Upper bound for Harmonic Numbers

We begin by discussing the famous upper bound for Harmonic Numbers:

This can be noted by observing the graph of $$$f(x) = \frac{1}{x}$$$ and drawing rectangles of base length 1 and height $$$\frac{1}{i}$$$ to get areas that sum up to $$$H_n$$$, similar to this (the image is taken from Stewart Calculus):

and so we have

(there is a known approximation using Euler-Mascheroni constant but I like this more simple proof).

This is why a loop like this:

for (int i = 1; i <= n; i++) 
    for (int j = i; j <= n; j += i) {
        // some constant code
    }

works in $$$O(n \log n)$$$, because $$$j$$$ iterates over all multiples of $$$i$$$ that are at most $$$n$$$, and there are $$$\displaystyle\left\lfloor \frac{n}{i} \right\rfloor$$$ such multiples, and so the complexity is just $$$\displaystyle\sum_{i = 1}^{n} \left\lfloor \frac{n}{i} \right\rfloor \le \sum_{i = 1}^{n} \frac{n}{i} = n H_n \in O(n \log n)$$$.

This is very useful whenever you want to brute force all divisors of numbers in a range $$$[1, N]$$$. This can be used to precompute the number, sum, product of divisors of all numbers in $$$[1, 10^6]$$$. You can even precompute the divisors themselves:

for (int i = 1; i <= n; i++) 
    for (int j = i; j <= n; j += i) divs[j].push_back(i);

This can also be used to calculate the Euler-Totient function $$$\varphi(n)$$$ and can be used in some inclusion-exclusion DP to precalculate the array $$$\text{dp}[x] = \sum_{i \lt j} [\gcd(a_i, a_j) = x]$$$ where $$$a_1, a_2, \dots, a_n$$$ is an array with $$$1 \le a_i \le 10^6$$$.

const int N = 1e6 + 9;
int a[N], cnt[N];
long long dp[N];
// input a[1], a[2], ..., a[n]
// ...
for (int i = 1; i <= n; i++) cnt[a[i]]++;
for (int i = N - 1; i >= 1; --i) {
    long long num_mul = 0; // number of multiples of i
    for (int j = i; j < N; j += i) num_mul += (long long)cnt[j];
    dp[i] = (num_mul * (num_mul - 1)) / 2; // number of pairs that are divisible by i
    for (int j = i + i; j < N; j += i) dp[i] -= dp[j]; // subtract all dp[j] for j > i and i divides j
}

Example problems: (feel free to add more in the comments)

• 1731E - Graph Cost

• 103373B - Aliquot Sum

• 101992D - The Millennium Prize Problems

2. Distinct values of $$$\left\lfloor\frac{n}{i}\right\rfloor$$$

Now, let's get to even more interesting facts:

We will discuss why this is true and how to retrieve the exact values over the exact ranges in $$$O(\sqrt{n})$$$.

Now, note that these values are non-increasing as $$$i$$$ increases. For example, for $$$n = 10$$$, we get the values (starting from $$$i = 1$$$) $$$10, 5, 3, 2, 2, 1, 1, 1, 1, 1, 0, 0, \dots$$$. So, to find these values, we will prove the following fact:

(note that I will write a mathematical proof and it may not seem intuitive to see, and I will explain its intricacies afterwards, so don't get shocked :D)

Now, what this proof is trying to say (skip these two paragraphs if you understand and can imagine the proof) is that if you get that $$$\displaystyle \left\lfloor \frac{n}{i} \right\rfloor = q$$$ for some $$$i$$$ and $$$q$$$, and again $$$\displaystyle \left\lfloor \frac{n}{i + 1} \right\rfloor = q$$$ as well, then we know for sure that $$$n \text{ mod } (i + 1) = (n \text{ mod } i) - q$$$ by the division algorithm. (If $$$n = qi + r = q(i + 1) + r'$$$ then $$$r' = r - q$$$).

This means that with every step forward, the remainder decreases by exactly the value of the floor division. So, the remainder is maximal at the first time we reach some value $$$q$$$ (at $$$l$$$), and the remainder keeps decreasing by $$$q$$$ until we can't decrease anymore (decreasing will makes the remainder negative), and so the floor division value becomes $$$q - 1$$$ instead. So, to find the maximum point at which the floor value stays the same $$$q$$$, we find the maximum $$$k$$$ such that $$$qk \le n \text{ mod } l$$$, which is $$$\left\lfloor \frac{n \text{ mod } l}{q} \right\rfloor$$$, and we add that value to $$$l$$$ to get the same conclusion.

This fact is very useful in optimizing solutions to many problems, and I will demonstrate this by solving one example: CSES — Sum of Divisors. (The reader is encouraged to solve this on his/her own before reading on).

The problem wants to find the summation of divisors of all integers up to $$$n$$$, but with $$$n \le 10^{12}$$$. This means that at most $$$O(\sqrt{n})$$$ complexity is required. Now, the idea here is to fix a divisor and count how many times it will be a divisor. Well, for a divisor $$$d$$$, the number of multiples of $$$d$$$ up to $$$n$$$ is $$$\displaystyle \left\lfloor \frac{n}{d} \right\rfloor$$$, so the answer is just

Here, to optimize, we can fix the value of $$$\displaystyle \left\lfloor \frac{n}{d} \right\rfloor$$$ and sum all $$$d$$$ that has this value. But from what we've arrived at from the above claim, we can easily do this:

const ll mod = 1e9 + 7;
ll n; cin >> n;
auto sum = [&](ll l, ll r) { // returns l + l + 1 + ... + r
    r %= mod, l %= mod;
    ll sum_r = (r * (r + 1))/2; sum_r %= mod;
    ll sum_l = (l * ((l - 1 + mod) % mod))/2; sum_l %= mod;
    return (sum_r - sum_l + mod) % mod;
};
for (ll l = 1, r = 1; (n/l); l = r + 1) {
    r = (n/(n/l));
    ans += (sum(l, r) * (n/l)) % mod;
    ans %= mod;
}
cout << ans << "\n";

The code iterates over ranges that have the same value of floor division when $$$n$$$ is divided by them and multiplies the floor division value by the sum of elements in the range, modulo $$$10^9 + 7$$$. Each time we calculate $$$r$$$ (as defined in Fact 3) and at the end of the iteration, we make the next $$$l$$$ as $$$r + 1$$$, since $$$r$$$ is the maximum then $$$r + 1$$$ will get a new floor division value. So, the idea is always to get the ranges of the same floor value and process them however you like

for (ll l = 1, r = 1; (n/l); l = r + 1) {
    r = (n/(n/l));
    // q = (n/l), process the range [l, r]
}

This fact also turns out to be useful in optimizing some Möbius inversion formulas.

Example problems: (feel free to add more in the comments)

• CSES — Sum of Divisors

• 1706D2 - Chopping Carrots (Hard Version)

• 102803H - Hate That You Know Me

Introduction

Some of you smart people out there may find the contents of this blog so obvious, that it does not deserve to be called a "technique." It is just the totally normal thought process that comes across our minds when we try to solve a problem!

However, I often find it useful (and others may relate) to state my thoughts explicitly when trying to conquer a problem, whether I write it down on a sheet of paper, comment it in my code, or just talk out loud like a crazy guy :D. I observe that one of the things that makes a problem-solver better than another (other than practice and knowledge about certain topics/algorithms, of course) is the way of thinking and approaching a problem. So, to make myself a better problem-solver, I sometimes go about thinking about how I think and try to improve this way of thinking generically and generally about any problem. It is, to many great problem-solvers, one of the byproducts of practicing problems a lot that develops implicitly, and stating such byproducts to myself explicitly is very helpful to me in order to speed up my learning process.

In this blog, I will try to explain a technique of thinking that I found recurring and often helpful in facing many problems that may seem daunting to many people at first sight, with an unorganized train of thought. Afterward, I will try to apply this technique to some Codeforces problems I solved that I found considerably not easy to go about when I haven't tried this technique explicitly. It is highly encouraged to try these problems out yourself before reading the solution (I know there are already posted great editorials for the problems, but I wrote the solution in my style in order to cope with the theme of this blog).

Disclaimer: I don't know if someone else posted something similar to this technique on Codeforces or outside Codeforces, and I tried to search but couldn't; that is why I thought of posting it myself.

The technique (Characteristics of the optimal solution)

A lot of the problems we face involve finding an optimal solution of some kind, e.g. find a subsequence that has minimum * something * or find a graph of an array that satisfies some requirements. The main technique is to think as follows:

Suppose I did find such a solution, what would it look like? what characteristics it would have? Can we toy around with such a solution so that it remains optimal?

From asking ourselves this question and trying to answer it, we are able to come up with very useful observations that help us in finding the solution. Moreover, the important thing is to have the courage to toy around with the solution and often you would try to reduce it while still satisfying the requirements (e.g. if a subsequence has a minimum * something *, can I reduce the number of elements in it so that it still has the minimum * something *?) If you still don't fully comprehend how useful this may be, don't worry; it will be more clear with the problems.

Problem 1. 1592C - Bakry and Partitioning

(Again, it is highly encouraged to try the problem out yourself if you haven't — before proceeding in this blog.)

So, the problem asks us to find a way to partition our tree into a forest, where each tree has the same bitwise XOR value as all the other trees. Let's try to apply our technique here:

Suppose I did find a way to partition my trees into a forest, and now I have a forest containing $$$q$$$ trees with the same bitwise XOR value $$$x$$$, are there any characteristics of these $$$q$$$ trees? Can I toy around with them a bit and reduce the number of trees?

In this problem, it would be useful to toy around with them.

We note that if we have a tree that we partitioned into 2 trees with XOR values $$$a$$$ and $$$b$$$, then it is clear that before partitioning, the whole tree had an XOR value of $$$a \oplus b$$$. That means that the kind of "toying around" we can do here is to merge two trees into one with and XOR their values. Now, let's get back to our optimal solution. If we try to merge two trees that both have an XOR value of $$$x$$$, then the resultant tree has an XOR value $$$x \oplus x = 0$$$ (don't worry, we didn't ruin the optimality of the solution). If we merge one more tree to the resultant tree, the final tree would have an XOR value of $$$x \oplus 0 = x$$$. So, if we have $$$q$$$ trees in our optimal solution, we can reduce them to $$$q - 2$$$ trees, and the solution would still remain optimal. So, if $$$q$$$ is even, we can reduce it to $$$2$$$ and if $$$q$$$ is odd we can reduce it to $$$3$$$. This means that if a solution exists with $$$q$$$ trees, then so does a solution with $$$q \mod 2 + 2$$$ trees, and we only need to check if we can cut one edge or two edges. The remaining part of the problem is some proper handling of the two cases which is irrelevant to this blog (you can check it out in the editorial if it is still a little difficult for you).

Problem 2. 1629D - Peculiar Movie Preferences

We note that if one string is a palindrome, then we are done (if there is a string of length 1, it would automatically be a palindrome, so we would assume that no strings are of length 1). Otherwise, let's apply our technique:

If a palindrome consists of multiple strings, what would they look like? Can I toy around with them a bit?

Now, it is important to note that if a string is a palindrome, then every prefix is also a suffix of the string. So, if we have a palindromic string consisting of strings of lengths 2 and 3, we can toy around with it by fixing the first string and the last string and drop those in between, and the string would still remain palindromic. This reduces the problem to finding two strings that can be concatenated to form a palindrome.

Problem 3. 1366D - Two Divisors

At first sight, the problem would make me scratch my head a while, asking recurrently "how do I find such divisors?". However, I try to apply this technique and ask:

Let's suppose I did find two divisors $$$d_1$$$ and $$$d_2$$$ where $$$\text{gcd}(d_1 + d_2, a_i) = 1$$$, what characteristics can those two divisors have?

Well it's important to note that $$$d_1$$$ and $$$d_2$$$ are divisors of $$$a_i$$$, but if $$$\text{gcd}(d_1 + d_2, a_i) = 1$$$, then for every prime $$$p|a_i$$$, $$$p \not | (d_1 + d_2) \implies p \not | d_1$$$ or $$$p \not | d_2$$$. This means that if there is a prime $$$p$$$ that divides $$$d_1$$$, it can not divide $$$d_2$$$, otherwise $$$\text{gcd}(d_1 + d_2, a_i) \ge p$$$, so we immediately conclude $$$\text{gcd}(d_1, d_2) = 1$$$, which can't happen if $$$a_i$$$ has one prime divisor, so we assume it would have more than one prime divisor.

If we look at such divisors, we note that if a prime $$$p$$$ does not divide both divisors, then it is possible that it may divide their sum (e.g. $$$5 | (2 + 3)$$$). However, if for every prime divisor of $$$a_i$$$, $$$p$$$ divides one of the two divisors and not the other, then we are certain that $$$p$$$ doesn't divide their sum (because if we assume WLOG $$$p | d_1$$$, then $$$d_1 + d_2 \equiv d_2 \pmod{p}$$$). This means we can partition the primes of $$$a_i$$$ into $$$d_1$$$ and $$$d_2$$$, and so each prime would divide one of the divisors and not the other. So, we can solve the problem by taking one prime divisor of $$$a_i$$$, p, that divides $$$a_i$$$ and divide $$$a_i$$$ by it until it's no longer divisible, and check if $$$a_i$$$ still remains more than 1 and if so, we would have our solution. That one prime divisor of $$$a_i$$$ can be found using normal sieve of eratosthenes.

Problem 4. 1343E - Weights Distributing

It can be apparent that we should distribute the weights on our path greedily, with the minimum having the highest priority. The number of edges we need to distribute the weights on has to be minimal, otherwise, we would need to use a new price from the given array. That way, our prices has to distribute on the edges that are on the shortest paths between $$$a$$$ and $$$b$$$ and $$$b$$$ and $$$c$$$, but an important thing to note is that in a graph, there can be multiple shortest paths.

Let's now ask ourselves: what would the shortest paths look like? What characteristics of the shortest path do we need in order to have them include the minimum price possible?

Ok, so the shortest paths can be one straight line from $$$a$$$ to $$$b$$$ and $$$b$$$ to $$$c$$$, that is the two paths $$$a \to b$$$ and $$$b \to c$$$ are not intersecting with only $$$b$$$ as a common node, otherwise, they would intersect in a considerable number of nodes, so our "optimal solution" would include at least one intersection point. We can fix a common node $$$x$$$, and our path would look like $$$a \to x$$$, $$$x \to b$$$, $$$b \to x$$$, then $$$x \to c$$$, with the common edges on the path $$$x \to b$$$ only. So, we would have to distribute the minimal prices on the edges that are on the path from $$$x \to b$$$ and then $$$a \to x$$$ and then $$$x \to c$$$ because our path would have $$$\text{dist}(a,x) + 2\text{dist}(b,x) + \text{dist}(c,x)$$$. So, we would store the shortest paths from $$$a, b,$$$ and $$$c$$$ using some shortest path algorithm like Dijkstra in 3 arrays, and iterate over $$$x$$$ and minimize $$$\text{pref}[\text{dist}(b,x)] + \text{pref}[\text{dist}(a,x) + \text{dist}(b,x) + \text{dist}(c,x)]$$$, where $$$\text{pref}$$$ is a prefix sum array, on the sorted array of prices.

Conclusion

I hope you found these ideas helpful and not a waste of time.

From my naïve perception, the whole of Competitive Programming can be partitioned into pure problem-solving and thinking skills, and techniques/topics/algorithms that one may learn to help him tackle some problems like graphs, Number Theory, DP, ... . The former part, I see, is implicit to most problem solvers and it is just part of their unorganized train of thought that becomes more and more organized with practice. But, I think it can also be structured, and taught. You can consider this blog's content as a technique to have some kind of organization of the train of thought; it's a help in the "pure problem-solving and thinking skills" part, not the topics/algorithms part.

(More practice problems will be added once I observe them. If you have some recommendations of good problems with this technique involved, please post them in the comments and I would add them to the blog).

Here are some practice problems:

• 233B - Non-square Equation
• 1064D - Labyrinth
• 1312E - Array Shrinking
• 1632C - Strange Test
• 1656B - Subtract Operation
• 1656D - K-good