Skip to content

Slope Trick Ladder

This ladder is for the exact convex-function DP lane where:

  • the state is one convex piecewise-linear function f(x)
  • one update adds a hinge like max(0, x-a) or max(0, a-x)
  • and movement sometimes widens the minimizer interval

Who This Is For

Use this lane if:

  • you can already define the DP state as "best answer when ending at coordinate x"
  • the state remains convex in that coordinate
  • the next step is no longer generic state design, but function maintenance

This lane is intentionally narrow:

  • one exact starter
  • one flagship in-repo rep with shift_min
  • one warm-up compare point where the same family is lighter

Warm-Up

Target skill:

  • recognize when plain median maintenance is the lighter route inside the same convex-function family

Core

Target skill:

  • map each contest event to one of:
  • add max(0, x-a)
  • add max(0, a-x)
  • add |x-a|
  • shift_min

Stretch

Target skill:

  • distinguish "same slope-trick machinery, different recurrence skin" from genuinely different optimization families

Retrieval Layer

Repo Anchors And Compare Points

The cleanest in-repo loop here is:

  1. learn the exact operations from the Slope Trick topic
  2. trust the starter through Snuketoon
  3. compare back against Absolute Minima so "slope trick vs lighter median route" becomes real

Exit Criteria

You are ready to move on when:

  • you can explain why the state stays convex
  • you can translate a transition into one hinge or one shift_min
  • you can say when Absolute Minima is the lighter same-family route
  • you can say why CHT / Li Chao is a different family

External Practice