Skip to content

Lagrangian Relaxation / Aliens Trick Hot Sheet

Use this page when the original problem asks for the best answer with exactly K choices, but the same problem becomes much cheaper if each choice costs a penalty lambda.

Do Not Use When

Exact Maximization Route

For fixed integer penalty lambda, solve:

\[ \max(\text{original value} - \lambda \cdot \text{count}) \]

and return:

  • penalized_value
  • count

For equal penalized values, prefer the larger count.

Then:

  • binary search the largest lambda with count >= K
  • recover:
answer = penalized_value + lambda * K

Recognition Cues

  • "choose exactly K intervals / segments / facilities / positions"
  • the count dimension is the only thing making the DP too expensive
  • editorial mentions Alien DP, wqs binary search, concavity, or Lagrangian relaxation

Core Invariants

  • the relaxed solver must return both value and count
  • count must move monotonically as lambda changes
  • tie-break direction is part of correctness, not style
  • integer slopes want integer binary search

Main Traps

  • tie-breaking equal values by smaller count in a maximization route
  • using floating-point search when the slopes are integral
  • forgetting to add lambda * K back
  • assuming a penalty with exact count K always exists

Exact Starter In This Repo

Reopen Paths