PrevNext
Rare
 0/8

Lagrangian Relaxation

Authors: Benjamin Qi, Alex Liang, Dong Liu

aka Aliens Trick

Edit This Page

Resources

Resources
Mamnoon Siam
Serbanology

Lagrangian Relaxation

Lagrangian Relaxation involves transforming a constraint on a variable into a cost λ\lambda and binary searching for the optimal λ\lambda.

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

The problem gives us a length NN (1N31051 \le N \le 3 \cdot 10^5) array of integers in the range [109,109][-10^9,10^9]. We are given some KK (1KN1 \le K \le N) and are asked to choose at most KK disjoint subarrays such that the sum of elements included in a subarray is maximized.

Intuition

The main bottleneck of any dynamic programming solution to this problem is having to store the number of subarrays we have created so far.

Let's try to find a way around this. Instead of storing the number of subarrays we have created so far, we assign a penalty of λ\lambda for creating a new subarray (i.e. every time we create a subarray we penalize our sum by λ\lambda).

This leads us to the sub-problem of finding the maximal sum and number of subarrays used if creating a new subarray costs λ\lambda. We can solve this in O(N)\mathcal{O}(N) time with dynamic programming.

Dynamic Programming Solution

Let vv be the maximal achievable sum with λ\lambda penalty and cc be the number of subarrays used to achieve vv. Then the maximal possible sum achievable if we use exactly cc subarrays is v+λcv+\lambda c. Note that we add λc\lambda c to undo the penalty.

Our goal is to find some λ\lambda such that c=Kc=K (assuming KK is at most the number of positive elements). As we increase λ\lambda, it makes sense for cc to decrease since we are penalizing subarrays more. Thus, we can try to binary search for λ\lambda to make c=Kc=K and set our answer to be v+λcv+\lambda c at the optimal λ\lambda.

This idea almost works but there are still some very important caveats and conditions that we have not considered.

Geometry

Let f(x)f(x) be the maximal sum if we use at most xx subarrays. We want to find f(K)f(K).

The first condition is that f(x)f(x) must be concave or convex. Since f(x)f(x) is increasing in this problem, the means that we need f(x)f(x) to be concave: f(x)f(x1)f(x+1)f(x)f(x) - f(x - 1) \ge f(x + 1) - f(x). In other words, this means that the more subarrays we add, the less we increase the sum by. We can intuitively see that this is true.

Proof that our function is concave

Consider the following graphs of f(x)f(x) and f(x)λxf(x)-\lambda x. In this example, we have λ=5\lambda=5.

Here is where the fact that f(x)f(x) is concave comes in. Because the slope is non-increasing, we know that f(x)λxf(x) - \lambda x will first increase, then stay the same, and finally decrease.

Let v(λ)v(\lambda) be the optimal maximal achievable sum with λ\lambda penalty and c(λ)c(\lambda) be the number of subarrays used to achieve v(λ)v(\lambda) (note that if there are multiple such possibilities, we set c(λ)c(\lambda) to be the maximal number of subarrays to achieve v(λ)v(\lambda)). These values can be calculated in O(N)\mathcal{O}(N) time using the dynamic programming approach described above.

When we assign the penalty of λ\lambda, we are trying to find the maximal sum if creating a subarray reduces our sum by λ\lambda. So v(λ)v(\lambda) will be the maximum of f(x)λxf(x) - \lambda x and c(λ)c(\lambda) will equal to the rightmost xx that maximizes f(x)λxf(x) - \lambda x.

Given the shape of f(x)λxf(x) - \lambda x, we know that f(x)λxf(x) - \lambda x will be maximized at all points where λ\lambda is equal to the slope of f(x)f(x) (these points are red in the graph above). If there are no such points it will be maximized at the rightmost point where the slope is less than λ\lambda. So this means that c(λ)c(\lambda) will be the rightmost xx at which the slope of f(x)f(x) is still greater or equal to λ\lambda.

Now we know exactly what λ\lambda represents: λ\lambda is the slope and c(λ)c(\lambda) is the rightmost xx at which the slope of f(x)f(x) is still greater or equal to λ\lambda.

We binary search for λ\lambda and find the highest λ\lambda such that c(λ)Kc(\lambda) \ge K. Let the optimal value be λopt\lambda_{\texttt{opt}}. Then our answer is v(λopt)+λoptKv(\lambda_{\texttt{opt}}) + \lambda_{\texttt{opt}} K. Note that this works even if c(λopt)Kc(\lambda_{\texttt{opt}}) \neq K since c(λopt)c(\lambda_{\texttt{opt}}) and KK will be on the same line with slope λopt\lambda_{\texttt{opt}} in that case.

Because calculating v(λ)v(\lambda) and c(λ)c(\lambda) with the dynamic programming solution described above will take O(N)\mathcal{O}(N) time, this solution runs in O(NlogA[i])\mathcal{O}(N\log{\sum A[i]}) time.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int main() {
int n, k;
cin >> n >> k;
int a[n];

Problems

StatusSourceProblem NameDifficultyTags
PlatinumEasy
CFNormal
CFNormal
FHCNormal
KattisNormal
Balkan OINormal
IOIHard

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext