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.


<
Previous Post
APIO 2025
>
Blog Archive
Archive of all previous blog posts