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.

Lagrange multipliers

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

in some cases (when $$$f$$$ and $$$g$$$ are continuously differentiable) can be reduced to the unconstrained optimization problem

Here $$$\lambda \cdot g(x)$$$ denotes the dot product of a variable vector $$$\lambda$$$ and $$$g(x)$$$. The reduction means that for any solution $$$x^*$$$ of the initial problem there exists $$$\lambda^*$$$ such that $$$(x^*, \lambda^*)$$$ is the solution to the unconstrained problem. We will consider two possible interpretations of this.

Geometrically, the idea behind Lagrange multipliers is that in the extreme point $$$x^*$$$, the tangent space to the constraint surface $$$g(x)=0$$$ should lie completely within the tangent space of the contour surface $$$f(x)=f(x^*)$$$. See the illustration below for 2D case.

For linear spaces, $$$A \subset B$$$ if and only if $$$B^\bot \subset A^\bot$$$ where $$$A^\bot$$$ is an orthogonal complement space of $$$A$$$. For a tangent space, its orthogonal complement is a normal space. For the surface $$$f(x)=d$$$, normal is a line formed by the gradient vector $$$\nabla f$$$. And for the surface $$$g(x)=0$$$, its normal is a linear space formed by the vectors $$$\nabla g_1 (x), \dots, \nabla g_c(x)$$$.

Thus, for the point $$$x^*$$$ to be the solution of constrained problem, $$$\nabla f(x^*)$$$ must be a linear combination of $$$\nabla g_1(x^*), \dots, \nabla g_c(x^*)$$$. This, in turn, is exactly the extreme point condition of $$$L(x, \lambda)$$$ and the $$$\lambda$$$ vector consists of coefficients of this linear combination.

Heuristically, you can perceive $$$\lambda$$$ as penalizing coefficients for violating $$$g(x)=0$$$.

Model problem

You're given an array $$$a_1, \dots, a_n$$$. You have to pick $$$k$$$ non-intersecting contiguous sub-arrays with maximum sum of elements.

Typical solution would be to consider $$$dp(i, j)$$$ as the maximum possible answer on first $$$i$$$ elements with $$$j$$$ sub-arrays.

References

• The Trick From Aliens — Serbanology
• My Take on Aliens' Trick — Mamnoon Siam's Blog
• Part of the article was once revealed to me in a dream