Quadrangle Inequality and Alien’s Trick
A function $f(\cdot, \cdot)$ satisfies quadrangle when for any $a \leq b$ and $c \leq d$, the inequality $f(a,c) + f(b,d) \leq f(a,d) + f(b,c)$.
If $f$ is viewed as a grid, then it means we find a submatrix (not contiguous 2x2 block) $\begin{pmatrix}w & x \\ y & z\end{pmatrix}$ and we require that $w+z \leq x+y$.
Actually, it is enough that this is satisfied for all submatrices that are contiguous 2x2 blocks. That is, $a+1=b$ and $c+1=d$.
Suppose the inequality is satisfied for $(a,a+1,c,d)$ and $(a+1,a+2,c,d)$.
Then we have $f(a,c)+f(a+1,d) \leq f(a,d) + f(a+1,c)$ and $f(a+1,c)+f(a+2,d) \leq f(a+1,d) + f(a+2,c)$.
Adding both inequalities and subtracting $f(a+1,c)+f(a+1,d)$ on each side, we obtain $f(a,c)+f(a+2,d) \leq f(a,d) + f(a+2,c)$.
Property 1: let $\text{opt}(r)$ denote the $l$ that minimizes $f(l,r)$. Then $\text{opt}(r) \leq \text{opt}(r+1)$.
Proof:
Suppose $\text{opt}(r) > \text{opt}(r+1)$. This means quadrangle is not satisfied for $(\text{opt}(r+1), \text{opt}(r), r, r+1)$ as we can write the inequalities $f(\text{opt}(r+1),r) > f(\text{opt}(r),r)$ and $f(\text{opt}(r),r+1) > f(\text{opt}(r+1),r+1)$.
Suppose we have a fucntion $f$ that satisfies quadrangle, we want to find a partition of $[1,n)$ into $m$ ranges $[l_1,r_1),[l_2,r_2), \ldots, [l_m,r_m)$ such that $l_1 = 1$, $l_i < r_i$, $r_i = l_{i+1}$ and $r_k=n$ and we also minimize $f(l_1,r_1) + f(l_2,r_2) + \ldots + f(l_m,r_m)$.
In other words, find indices $1 = i_1 < i_2 < \ldots < i_{m+1} =n$ such that $f(i_1,i_2) + f(i_2,i_3) + \ldots + f(i_m,i_{m+1})$.
Let $\text{dp}(i,k)$ denote the best partition of $[1,i]$ into $k$ ranges. The obvious dp is $\text{dp}(i,k) = \min(\text{dp}(j,k-1) + f(j,i))$.
Property 2: For a fixed $k$, Let $\text{opt}_k(i)$ be the value of $j$ that minimizes $\text{dp}(j,k-1) + f(j,i)$. Then $\text{opt}_k$ is monotone.
Proof:
Let $g_k(j,i) = \text{dp}(j,k-1) + f(j,i)$. Then we want to show that $g_k$ satisfies quadrangle.
$\begin{align} g_k(a,c) + g_k(b,d) &= \text{dp}(a,k-1) + \text{dp}(b,k-1) + f(a,c) + f(b,d) \\&\leq \text{dp}(a,k-1) + \text{dp}(b,k-1) + f(a,d) + f(b,c) \\ & = g_k(a,d) + g_k(b,c) \end{align}$.
Therefore, by property 1, $\text{opt}_k(i)$ is monotone.
Property 3: For a fixed $i$, Let $\text{opt}_i(k)$ be the value of $j$ that minimizes $\text{dp}(j,k-1) + f(j+1,i)$. Then $\text{opt}_i$ is monotone.
Proof:
Consider the splitting points $p_1,p_2,\ldots,p_k,p_{k+1}$ and $q_1,q_2,\ldots,q_{k+1},q_{k+2}$ used in the solutions of $\text{dp}(i,k)$ and $\text{dp}(i,k+1)$ respectively.
Here, $p_1 = q_1$ and $p_{k+1} = q_{k+2}$.
Note that $p_k = \text{opt} _ k(p _ {k+1})$ and $q_k = \text{opt} _ k(q _ {k+1})$.
By induction and property 2, we have $q_i \leq p_i$.
Notice that if we reverse the array, we also get $p_i \leq q_{i+1}$.
Combining these two, we get $p_i \leq q_{i+1} \leq p_{i+1}$.
But actually, we only really needed the last inequality to show that $\text{opt}i(k) = p_k \leq q{k+1} = \text{opt}_i(k+1)$.
Property 4: $\text{dp}(i, \cdot)$ is convex.
Proof:
We want to show that $2 \text{dp}(i,k+1) \leq \text{dp}(i, k) + \text{dp}(i, k+2)$.
Generally, the way to accomplish this is to take the solutions for $\text{dp}(i, k)$ and $\text{dp}(i, k+2)$ and mix them in two different ways to obtain two candidate solutions for $\text{dp}(i,k+1)$ whose sum of costs is at most $\text{dp}(i, k) + \text{dp}(i, k+2)$.
Consider the splitting points $p_1,p_2,\ldots,p_k,p_{k+1}$ and $q_1,q_2,\ldots,q_{k+2},q_{k+3}$ used in the solutions of $\text{dp}(i,k)$ and $\text{dp}(i,k+2)$ respectively.
It is clear that we have $p_{i-2} \leq q_i \leq p_i$, refer to the proof of property 3.
If $p_i = q_{i+1}$ for some $i$, then we win. We can use the splitting points $p_1,p_2,\ldots,p_i=q_{i+1},q_{i+2},\ldots,q_{k+3}$ and $q_1,q_2,\ldots,q_{i+1}=p_i,p_{i+1},\ldots,p_{k+1}$ as two possible candidates for $\text{dp}(i,k+1)$. Then the sum of costs these two candidates are exactly $\text{dp}(i, k) + \text{dp}(i, k+2)$.
Let us associate each $q_i$ with $\texttt{0}$ if $p_{i-2} \leq q_i < p_{i-1}$ and $\texttt{1}$ if $p_{i-1} < q_i \leq p_i$. This gives us some binary string $s$ associated with $p$.
It is clear that the first and last characters of $s$ are $\texttt{1}$ and $\texttt{0}$ respectively.
Now, $\texttt{10}$ appears as a substring in $p$, that means we can find some $i$ such that $p_{i-1} < q_i < q_{i+1} < p_i$.
Consider the splitting points $p_1,p_2,\ldots,p_{i-1},q_{i+1},q_{i+2},\ldots,q_{k+3}$ and $q_1,q_2,\ldots,q_i,p_i,p_{i+1},\ldots,p_{k+1}$ as two possible candidates for $dp(i,k+1)$.
Notice that the total cost of the two candidates after subtracting the cost of $\text{dp}(i, k) + \text{dp}(i, k+2)$ is $f(p_{i-1},q_{i+1}) + f(q_i,p_i) - f(p_{i-1},p_i) - f(q_i,q_{i+1})$ which we know is $\leq 0$ by quadrangle.
By property 4, we can do Alien’s trick.