In solving a problem, it is often difficult to obtain the optimal solution due to strict constraints, making it computationally expensive. Lagrange Relaxation is a method that loosens some particular constraints of the problem with the objective to optimize the findings. This is done by introducing Lagrange multipliers for those relaxed constraints. The solution to the problem with the relaxed constraints is then used as the boundary (both upper and lower) for the original problem.

The Aliens problem from IOI 2016 brought significant attention for this method, making it also known as Aliens' Trick. Ever since, this method has started to gain popularity among competitive programmers. In this blog, we will delve deeper into this method; especially in solving the Aliens problem. If you are not familiar with the Convex Hull Trick yet, I suggest you to read my blog here.

Motivational Problem: IOI 2016 - Aliens

We have a low-resolution photo of a remote planet's area, which is divided into an

KaTeX can only parse string typed expression

m \times m

grid consisting of

n

points that we are interested in. Our satellite, passing over the main diagonal of the grid, can take high-resolution photos of square areas. Each square's opposite corners must be on the grid's main diagonal. The satellite can take at most

k

high-resolution photos. Our task is to choose up to

k

square areas to photograph ensuring:

Every cell with a point of interest is captured.
The total number of photographed cells is minimized.

We want to find the smallest possible total number of photographed cells.

Constraints

$1 \leq k \leq n \leq 1 0^{5}$
$1 \leq m \leq 1 0^{6}$

Subtasks

no.	points	$n$	$m$	$k$
1 - 3	$25$	$\leq 500$	$\leq 1000$
4	$16$	$\leq 4000$
5	$19$	$\leq 50000$		$\leq 100$
6	$40$

On contest score distribution

Naive Dynamic Programming (25 points)

Notice that due to constraint of "each square's opposite corners must be on the grid's main diagonal", we can always interchange the value of

KaTeX can only parse string typed expression

r_{i}

and

c_{i}

as the new point is a reflection point across the main diagonal. As a result, the order of

r_{i}

and

c_{i}

is irrelevant. For each point

i

, visualize it as a segment that spans the range

[l_{i}, r_{i}] = [min (r_{i}, c_{i}), max (r_{i}, c_{i})]

. Consequently, a photo that covers a point

(a, a)

(b, b)

will capture point

i

if and only if

a \leq l_{i} \leq r_{i} \leq b

Further, this observation indicates that capturing a point

KaTeX can only parse string typed expression

j

(

i < j

) will also encompass point

i

l_{j} \leq l_{i} \leq r_{i} \leq c_{j}

. With that, we may simply discard point

i

. After such eliminations, all remaining points will have the property: for points

i

and

j

(

i < j

r_{i} < r_{j}

and

c_{i} < c_{j}

Let

KaTeX can only parse string typed expression

dp_{i, j}

denotes the minimum cost to cover first

i

points with at most

j

photos. Then,

dp_{0, j} dp_{i, j} = 0 = t < i min dp_{t, j - 1} + (r_{i} - l_{t + 1} + 1)^{2} - max (r_{t} - l_{t + 1} + 1, 0)^{2}

Here is a breakdown of the components:

The $dp_{t, j - 1}$ represents the cost of capturing the first $t$ points using $j - 1$ photos. Then, we aim to cover the point $t + 1$ up to point $i$ using $1$ photo.
The expression $(r_{i} - l_{t + 1} + 1)^{2}$ calculates the cost of capturing the point $t + 1$ up to point $i$ using $1$ photo.
The $max (r_{t} - l_{t + 1} + 1, 0)^{2}$ part is accounted to an overcharging cost due to the overlap between point $t$ and point $t + 1$ . Hence, it is substracted to correct the cost.

This dynamic programming solution works in

KaTeX can only parse string typed expression

O (n^{2} k)

Convex Hull Trick (60 points)

We had:

dp_{0, j} dp_{i, j} = 0 = t < i min dp_{t, j - 1} + (r_{i} - l_{t + 1} + 1)^{2} - max (r_{t} - l_{t + 1} + 1, 0)^{2}

Our dynamic programming can be expressed as:

dp_{0, j} dp_{i, j} = 0 = t < i min (m_{t, j - 1} \cdot x_{i, j} + c_{t, j - 1}) + C_{i, j}

where:

$m_{t, j - 1} = - 2 (l_{t + 1} - 1)$
$x_{i, j} = r_{i}$
$c_{t, j - 1} = dp_{t, j - 1} + (l_{t + 1} - 1)^{2} - max (r_{t} - l_{t + 1} + 1, 0)^{2}$
$C_{i, j} = r_{i}^{2}$

This Convex Hull Trick approach runs about an

KaTeX can only parse string typed expression

O (kn)

armortized time. Note that it is not

O (kn lo g n)

as we can use a

std::deque

instead of a

std::vector

here, given that the point queries are in increasing order.

Lagrange Relaxation (100 points)

The following solution idea is inspired by and adapted from the official solution.

Denote

KaTeX can only parse string typed expression

f (i, j)

to be a function that represents our dynamic programming solution, i.e.

f (i, j) = dp_{i, j}

. We want to relax the constraints on the number of photos taken. Let's assume we don't have the

k

constraint and we want to apply a cost on each photo taken to make up for it. Define

L (i, j, λ)

to be

f (i, j) + λj

, implying an additional cost of

λ

for each photo taken.

For a

KaTeX can only parse string typed expression

λ

, we may define

g (i)

to represent another optimization problem that satisfies the following:

g (i) = k = 1 min n L (i, k, λ) = k = 1 min n f (i, k) + λk = t < i min g (t) + (r_{i} - l_{t + 1} + 1)^{2} - max (r_{t} - l_{t + 1} + 1, 0)^{2} + λ

Solving

KaTeX can only parse string typed expression

g (n)

for a given

λ

allows us to obtain the minimum number of photos required to capture all

n

points and achieve the minimum cost when each photo is charged

λ

cost, let's define it as

p (λ)

A function

KaTeX can only parse string typed expression

f (i, j)

is said to be convex if it satisfies:

f (i, j - 1) - f (i, j) \geq f (i, j) - f (i, j + 1)

. Alternatively, we may conclude a function

f (i, j)

to be convex if it is in the form:

f (i, j) = t < i min f (t, j - 1) + C (t + 1, i)

and

KaTeX can only parse string typed expression

C (x, y)

is a Monge Array, i.e.

\forall x, y

, it holds

C (x, y) + C (x + 1, y + 1) \leq C (x, y + 1) + C (x + 1, y)

. Claim that

f (i, j)

is convex; then, we want to prove that

C (x, y) = (r_{y} - l_{x} + 1)^{2} - max (r_{x - 1} - l_{x} + 1, 0)^{2}

is a Monge Array.

Convexity of f(i, j)

Based on the previous observations, we have

KaTeX can only parse string typed expression

r_{i} < r_{j}

and

c_{i} < c_{j}

for points

i

and

j

when

i < j

holds.

(l_{x + 1} - l_{x}) (r_{y + 1} - r_{y}) \geq 0 \Rightarrow r_{y} (l_{x} - 1) + r_{y + 1} (l_{x + 1} - 1) - r_{y} (l_{x + 1} - 1) - r_{y + 1} (l_{x} - 1) \geq 0 \Rightarrow (r_{y} - l_{x} + 1)^{2} + (r_{y + 1} - l_{x + 1} + 1)^{2} - (r_{y} - l_{x + 1} + 1)^{2} - (r_{y + 1} - l_{x} + 1)^{2} \leq 0 \Rightarrow C (x, y) + C (x + 1, y + 1) - C (x + 1, y) - C (x, y + 1) \leq 0 \Rightarrow C (x, y) + C (x + 1, y + 1) \leq C (x + 1, y) + C (x, y + 1)

It is shown that

KaTeX can only parse string typed expression

C (x, y)

is a Monge Array; hence,

f (i, j)

is convex.

Given that

KaTeX can only parse string typed expression

f (i, j)

is convex, so is

L (i, j, λ)

. This implies:

p (λ) = min x s.t. L (n, x, λ) \leq L (n, x + 1, λ) = min x s.t. f (n, x) - f (n, x + 1) \leq λ

With that we may find

KaTeX can only parse string typed expression

λ_{k} \in [0, m^{2}]

that satisfies

k \leq p (λ_{k})

and

p (λ_{k} + 1) \leq k

. This can be done using binary search with

O (n lo g m)

time complexity (the linear

n

is obtained from computing

g (n)

using Convex Hull Trick).

Last, we only need to find the exact value of

KaTeX can only parse string typed expression

f (n, k)

, which is our original objective. The interval

[p (λ_{k} + 1), p (λ_{k})]

signifies the range we are interested in. Considering that

\forall i \in [p (λ_{k} + 1), p (λ_{k}) - 1] : f (n, i) - f (n, i + 1)

remains constant (slope is constant), we may use linear interpolation to calculate our answer to the original problem. Let

Δ = f (n, p (λ_{k})) - f (n, p (λ_{k} + 1))

; then,

f (n, k) = f (n, p (λ_{k})) - (k - p (λ_{k})) \frac{Δ}{p ( λ _{k} + 1 ) - p ( λ _{k} )}

The overall solution operates in

KaTeX can only parse string typed expression

O (n lo g n + n lo g m)

Lagrange Relaxation in General

Basic Idea

Decomposition of the Original Problem: Decompose the original problem into a blend of a simpler optimization problem and an added term to penalize constraint violations.
Lagrange Function Formulation: In the equation below,
KaTeX can only parse string typed expression
$f (x)$ represents the objective function, $g (x)$ denotes the constraint equations, $b$ stands for their boundaries, and $λ$ acts as the Lagrange multiplier:
$L (x, λ) = f (x) + λ (g (x) - b)$
Bounds Identification: Establish both the lower and upper bounds wherein the solution to the original problem lies within the defined interval.

Importance of Convexity

Guaranteed Global Optima: Convexity ensures that the solution obtained from the relaxed problem, supported by Lagrange multipliers, offers a valid and global optimum bound.
Optimization Simplification: A convex optimization landscape simplifies the process, reducing potential local minima or maxima that can complicate the search for an optimal solution.
Efficient Solutions: When the Lagrange function is convex, it facilitates the efficient determination of the solution for the relaxed problem. This is important since Lagrange relaxation primarily aims to transform intricate problems into manageable sub-problems.

References

Chethiya Abeysinghe, "IOI 2016 - Solutions," International Olympiad in Informatics.
Mamnoon Siam, "Attack on Aliens," Siam's Blog. https://mamnoonsiam.github.io/posts/attack-on-aliens.html.
upobir, "Quadrangle Inequality Properties," Codeforces. https://codeforces.com/blog/entry/86306.

← [Tutorial] Li Chao Tree [Tutorial] Principal Component Analysis →

1

10

11

12

13

14

15

16

17

18

19

2

20

2020-Fall

2021-Fall

2021-Spring

2021-Summer

2022-Fall

2022-Spring

2023-Fall

2023-Spring

2024-Spring

20K-smooth

20K-smooth (no image)

21

22

23

24

25

26

27

28

29

3

30

31

32

33

34

35

36

37

4

5

6

7

8

9

appendix

appendix

appendix

archive

BIO1001-General-Biology

bonus

bonus

bucketsort

CHM1001-General-Chemistry

collections

Competitive-Programming

components

cpu

CSC1001-Introduction-to-Computer-Science-Programming-Methodology

CSC1002-Computational-Laboratory

CSC3001-Discrete-Mathematics

CSC3002-Assignment-1-src

CSC3002-Assignment-2-src

CSC3002-Assignment-3-src

CSC3002-Assignment-4-src

CSC3002-Assignment-5-src

CSC3002-Assignment-6-src

CSC3002-Introduction-to-Computer-Science-Programming-Paradigms

CSC3050-Computer-Architecture

CSC3050-Project-1-assembler

CSC3050-Project-2-simulator

CSC3050-Project-3-verilog

CSC3050-Project-4-CPU

CSC3100-Data-Structures

CSC3150-Assignment-1

CSC3150-Assignment-2

CSC3150-Assignment-3