Considering the Alien’s Trick (or Lagrange relaxation), it is sufficient to find the profit when one dinner party costs \(c\) for all \(1\leq c \leq M\).

Let’s consider the problem for a fixed \(c\). In fact, it can be formulated as an LP (※), and taking its dual gives the following problem:

• Choose some intervals \([L_i,R_i]\). There must not be an overlap of \(c+1\) or more intervals. What is the maximum number of intervals that can be taken?

Strictly speaking, the profit corresponding to \(c\) is the value obtained by subtracting the answer to the above problem from \(M\), but since it is the same thing, we will solve it in the form above.

\(c=1\) is a well-known problem that can be solved by the following greedy algorithm:

• Place a cursor at \(0\). Then, repeat the following operation.

• Take an interval that satisfies the following conditions and set the cursor to the right end of that interval.

  • The left end is to the right of the cursor.
  • The right end is the smallest among those intervals satisfying the above.

• Terminate when no more intervals can be taken.

In fact, the same can be done for \(c>1\). Suppose you have found a solution for \(c=x\). You can get a solution for \(c=x+1\) if you run almost the same greedy algorithm on the intervals that have yet to be used. It is “almost” the same, so there is a difference. After setting the cursor to the right end of the interval, you can move back to the left. The condition for moving back is: look at how many of the intervals used so far overlap, and as long as it is less than \(c\), you can move back.

The validity of the above greedy algorithm can be understood by considering what happens when the above problem is solved with flow.

This greedy algorithm can be executed in \(O(M \log M)\) time by using binary search on a lazy evaluation Segment Tree, etc.

The total computational complexity is \(O(N+M \log M)\). The TL is set a little strict to distinguish it from \(O(M\sqrt{M}\log(M))\) solutions. So, \(O(M \log^2M)\) solutions may not be accepted without small constant factors.

Sample Implementation

※ On the formulation as an LP

Create a minimization problem. Prepare variables \(x_0,x_1,\cdots,x_N\). Let \(x_i-x_{i-1}\) correspond to the number of times a dinner party is held on day \(i\). In other words, create a constraint \(x_{i-1} \leq x_i\) and a cost function \(K(x_N-x_0)\).

For each \((L_i,R_i)\), first introduce a variable \(d_i\) and let it correspond to whether there is a dinner party in the interval \([L_i,R_i]\). It is sufficient to add the constraints \(0 \leq d_i \leq 1, d_i \leq x_{R_i}-x_{L_i-1}\), and the cost function \(1-d_i\).

It can be proven from the totally unimodular property that this LP has an integer solution. It can also be proven via the dual problem. The details of this part are omitted.

If you consider the dual problem of this LP, it will have almost the same form as the min-cost flow. Further simplifying this leads to the problem described above.