Hi everyone!

This time I'd like to write about what's widely known as "Aliens trick" (as it got popularized after 2016 IOI problem called Aliens). There are already some articles about it here and there, and I'd like to summarize them, while also adding insights into the connection between this trick and generic Lagrange multipliers and Lagrangian duality which often occurs in e.g. linear programming problems.

Lagrange duality

Let $$$f : X \to \mathbb R$$$ be the objective function and $$$g : X \to \mathbb R^c$$$ be the constraint function. The constrained optimization problem

in some cases can be reduced to finding stationary points of the Lagrange function

Here $$$\lambda \cdot g(x)$$$ is the dot product of $$$g(x)$$$ and a variable vector $$$\lambda \in \mathbb R^c$$$, called the Lagrange multiplier. Mathematical optimization typically focuses on finding stationary points of $$$L(x,\lambda)$$$. However, in our particular case we're more interested in the function

which is called the Lagrange dual function. If $$$x^*$$$ is the solution to the original problem, then $$$t(\lambda) \leq L(x^*,\lambda)=f(x^*)$$$.

This allows to introduce the Lagrangian dual problem $$$t(\lambda) \to \max$$$. Note that $$$t(\lambda)$$$, as a point-wise infimum of concave (specifically, linear) functions, is always concave, even when $$$X$$$ is, e.g., discrete. If $$$\lambda^*$$$ is the solution to the dual problem, the value $$$f(x^*) - t(\lambda^*)$$$ is called the duality gap. We're specifically interested in the case when it equals zero, which is called the strong duality.

Typical example here is Slater's condition, which says that strong duality holds if $$$f(x)$$$ is convex and there exists $$$x$$$ such that $$$g(x)=0$$$.

Change of domain

In competitive programming, the set $$$X$$$ in definitions above is often weird and very difficult to analyze directly, so Slater's condition is not applicable. As a typical example, $$$X$$$ could be the set of all possible partitions of $$$\{1,2,\dots, n\}$$$ into non-intersecting segments.

To mitigate this, we define $$$h(y)$$$ as the minimum value of $$$f(x)$$$ subject to $$$g(x)=y$$$. In this notion, the dual function is written as

where $$$Y=\{ g(x) : x \in X\}$$$. The set $$$Y$$$ is usually much more regular than $$$X$$$, as just by definition it is already a subset of $$$\mathbb R^c$$$. The strong duality condition is also very clear in this terms: it holds if and only if $$$0 \in Y$$$ and there is a $$$\lambda$$$ for which $$$y=0$$$ delivers infimum.

Geometrically $$$t(\lambda)$$$ defines a level at which the epigraph of $$$h(y)$$$, i. e. the set $$$\{(y,z) : z \geq h(y)\}$$$ has a supporting hyperplane with the normal vector $$$(-\lambda, 1)$$$. Indeed, the half-space bounded by such hyperplane on the level $$$c$$$ is defined as

With $$$c=t(\lambda) > -\infty$$$, all the points at which the hyperplane touches the epigraph would correspond to infimum. Please, refer to the picture below. Lower $$$c$$$ would move the hyperplane lower, while higher $$$c$$$ would move it upper. With $$$c=t(\lambda)$$$, the hyperplane is lowest possible while still intersecting the epigraph of the function in the point $$$(y^*, h(y^*))$$$ where $$$y^*$$$ delivers the minimum of $$$h(y) - \lambda \cdot y$$$.

Competitive programming problems typically assume variable $$$y$$$ in the input, so for strong duality to hold for all inputs, all $$$y \in Y$$$ should have a supporting hyperplane that touches the epigraph in the point $$$(y, h(y))$$$. This condition is equivalent to $$$h(y)$$$ being convex on $$$Y$$$.

Monotonicity of $$$y_\lambda$$$

While calculating $$$t(\lambda)$$$, we typically find $$$x_\lambda$$$ that delivers the infimum of $$$f(x) - \lambda \cdot g(x)$$$. But at the same time we find $$$y_\lambda=g(x_\lambda)$$$ that delivers the infimum of $$$h(y) - \lambda \cdot y$$$. As $$$h(y)$$$ is convex, it is also convex component-wise, which means that increasing $$$y_i$$$ would generally require larger values of $$$\lambda_i$$$ in the supporting plane when all the other components of $$$y$$$ are fixed.

We can do a nested binary search on the components of $$$\lambda$$$ to find the $$$\lambda$$$ that corresponds to $$$y=0$$$. The procedure would look like this:

void adjust(double *lmb, int i, int c) {
    if(i == c) {
        return;
    }
    double l = -inf, r = +inf; // some numbers that are large enough
    while(r - l > eps) {
        double m = (l + r) / 2;
        lmb[i] = m;
        adjust(lmb, i + 1, c);
        auto [xl, yl] = solve(lmb); // returns (x_lambda, y_lambda) the minimum y_lambda[i]
        if(yl[k] < 0) {
            l = m;
        } else {
            r = m;
        }
    }
}

Note that a concrete $$$\lambda_i$$$ might correspond to the contiguous segment of $$$y_i$$$ and vice versa, thus we should find the $$$(x_\lambda,y_\lambda)$$$ pair with the minimum possible $$$i$$$-th component of $$$y_\lambda$$$ to guarantee monotonicity, otherwise binary search might work in an unexpected way.

Integer search

Here and onwards we refer to $$$h(y_i)$$$ as a function of single real variable $$$y_i$$$, assuming that all other components of $$$y$$$ are fixed.

What are the possible $$$y_i$$$ for specific $$$\lambda_i$$$? By definition, it implies $$$h(y_i)-\lambda y_i = h(y'_i) - \lambda y'_i$$$, thus the relationship between them is

What are the possible $$$\lambda_i$$$ for specific $$$y_i$$$? When $$$h(y_i)$$$ is continuously differentiable, it essentially means that $$$\lambda_i$$$ corresponds to $$$y_i$$$ such that $$$\lambda_i = h'(y_i)$$$. On the other hand, when $$$Y$$$ is the set of integers, $$$y_i$$$ optimizes $$$t(\lambda)$$$ for all $$$\lambda_i$$$ such that

So, if $$$h(y_i)$$$ is an integer function, we may do the integer search on $$$\lambda_i$$$ between minimum and maximum values of $$$h(k)-h(k-1)$$$.

In a very generic case, when the function is not continuously differentiable and $$$y_i$$$ are not necessarily integer, the set of possible $$$\lambda_i$$$ for a given $$$y_i$$$ is defined as $$$\partial h(y_i)$$$, the so-called sub-differential of $$$h$$$ in $$$y_i$$$, formally defined as $$$[a,b]$$$ where

The concept of sub-derivatives and sub-differentials can be generalized to multi-dimensional case as well with sub-gradients.

Problem examples

References

• Duality (optimization) — English Wikipedia
• The Trick From Aliens — Serbanology
• My Take on Aliens' Trick — Mamnoon Siam's Blog
• Incredibly beautiful DP optimization from N^3 to N log^2 N
• Comment on Codeforces by _h_
• Part of the article was once revealed to me in a dream