Skip to content

Monster Game II

  • Title: Monster Game II
  • Judge / source: CSES
  • Original URL: https://cses.fi/problemset/task/2085
  • Secondary topics: Li Chao tree, Affine DP, Line container
  • Difficulty: hard
  • Subtype: Online affine-DP optimization with arbitrary line/query order
  • Status: solved
  • Solution file: monstergame2.cpp

Why Practice This

This is the cleanest in-repo anchor for the exact Li Chao route inside the CHT / Li Chao family.

The problem gives a recurrence family where:

  • every previously killed monster offers one affine candidate
  • the current monster contributes only the query point s_i
  • the order constraints stay online

So the lesson is not "some random advanced trick."

It is:

  • derive one line from each previous state
  • keep an exact online minimum structure
  • know why Monster Game I is lighter, but Monster Game II wants the generic route

Recognition Cue

Reach for CHT / Li Chao when:

  • the recurrence becomes min_j(m_j x_i + b_j)
  • each previous choice contributes one line
  • the current item only contributes the query point
  • query order or slope order is not monotone enough for a deque hull

The strongest smell here is:

  • "minimum cost after any previous checkpoint," where the algebra isolates one product f_j * s_i

Problem-Specific Transformation

Let dp[i] be the minimum total time after killing monster i.

If the last previously killed monster is j, then the current kill cost is:

\[ dp[j] + f_j \cdot s_i \]

So state j contributes the line:

\[ y = f_j x + dp[j] \]

and current monster i asks for that line minimum at:

\[ x = s_i \]

The initial skill factor x is just the first line:

\[ y = x \cdot x' + 0 \]

where x' is the query coordinate.

So the problem becomes:

  • insert initial line (m = x, b = 0)
  • for each monster in order:
  • query at s_i
  • that answer is dp[i]
  • insert new line (m = f_i, b = dp[i])

Core Idea

Use a Li Chao tree for minimum queries over the domain of monster strengths.

Each node owns an x interval and stores the line that is currently best at that interval midpoint.

When a new line arrives:

  • compare it against the stored line at the midpoint
  • keep the midpoint winner in the node
  • recurse with the loser only into the side where it can still become better

That keeps insertion logarithmic.

For each monster:

  1. query the minimum value at s_i
  2. store it as dp[i]
  3. insert the line generated by f_i

This is exact, online, and does not need monotone slope/query order.

Complexity

If S is the integer strength domain width, then:

  • each query: O(log S)
  • each line insertion: O(log S)
  • total: O(n log S)

For CSES:

  • n <= 2 * 10^5
  • s_i, f_i <= 10^6

so the solution fits comfortably.

Pitfalls / Judge Notes

  • Use long long for dp, but evaluate m * x + b with __int128 inside the line container.
  • Insert the initial line from the starting skill factor before processing any monster.
  • This lane is minimum, not maximum.
  • Monster Game I has monotonicity that can support a lighter hull; Monster Game II removes that comfort.
  • Use the min/max strength range as the Li Chao domain, or another domain that definitely covers every query.

Reusable Pattern

Solutions