Solution to subproblem

As a subproblem, we consider the minimum fatigue for a fixed set of problems in one day.
First, for problems with \(A = 1\), we can consider that he solves them lastly on that day.
We consider the order of problems with \(A \geq 2\). The fatigue required to solve problems \(p\) and \(q\) consecutively in this order is less than solving \(q\) and \(p\) in this order if and only if

\[ \begin{aligned} &A_q(A_p x + B_p) + B_q \lt A_p(A_q x + B_q) + B_p \\ &\iff A_q B_p + B_q \lt A_p B_q + B_p \\ &\iff B_p(A_q - 1) \lt B_q(A_p - 1) \\ &\iff \frac{B_p}{A_p - 1} \lt \frac{B_q}{A_q - 1}, \end{aligned} \]

where \(x\) is the fatigue before solving those problems. Thus, it is optimal to solve the problems with \(A \geq 2\) in ascending order of \(\frac{B}{A-1}\) (tie broken arbitrarily), and then solve the problem with \(A=1\).

The property of cost function

Using the ordering above, one can see the following fact as a clue to the original problem:

Let the function \(f(S)\) be the minimum energy consumed required to solve all problems in a set \(S\).
Then, for two sets of problems \(S\) and \(T\) such that \(S \subseteq T\), and a problem \(p\) not contained in \(T\),

\[f(S \cup \lbrace p \rbrace) - f(S) \leq f(T \cup \lbrace p \rbrace) - f(T).\]

(Proof) If \(A_p=1\), then obviously the equality holds. We now assume that \(A_p \geq 2\).

Let \(v_1, \dots,v_i, p, v_{i+1}, v_n\) be the sequence of the problems in \(T \cup \lbrace p \rbrace\), sorted in ascending order of \(\frac{B}{A-1}\).
Let \(w_1, \dots, w_j, p, w_{j+1}, \dots, w_m\) be the sequence of the problems in \(S \cup \lbrace p \rbrace\), sorted in ascending order of \(\frac{B}{A-1}\); then, \(w_1, \dots, w_j\) is a subsequence of \(v_1, \dots, v_i\), and \(w_{j+1}, \dots, w_m\) is a subsequence of \(v_{i+1}, \dots, v_{n}\).

Consider the operation of solving a problem as an application of affine transform. (In other words, suppose you initially have \(x\), every time you solve a problem you apply \(Ax+B\), and finally assign \(x=0\).)
When a sequence of problems \(s\) is a subsequence of another \(t\), comparing “the linear function obtained by solving \(s\) in this order” and “the linear function obtained by solving \(t\) in this order,” we can prove that the latter has greater coefficients of both \(1\)-st and \(0\)-th degree than the former.

• Outline of proof: it can be shown by induction based on the following two facts.
  • If \(b \geq 0, a,c,d \geq 1\), then applying an affine transform \(ax+b\) to \(cx+d\) yields \(c(ax + b) + d = ac x + bc + d\), where \(ac \geq a\) and \(bc + d \geq b\). If you solve a problem when you have \(ax+b\), the two coefficients remain the same or become larger.
  • Also, if \(1 \leq a \leq a'\) and \(0 \leq b \leq b'\), then for \(c, d \geq 1\) it holds that \(a'c \geq ac\) and \(b'c + d \geq bc + d\). Thus, if you solve a problem when \(ax+b\) and \(a'x + b\), the relations \(a \leq a'\) and \(b \leq b'\) still hold.

Now, let

• \(ax + b\) be a linear function corresponding to \(w_1, \dots, w_j\);
• \(a'x + b'\) be a linear function corresponding to \(v_1, \dots, v_i\) ;
• \(cx + d\) be a linear function corresponding to \(w_{j+1}, \dots, w_m\);
• \(c'x + d'\) be a linear function corresponding to \(v_{i+1}, \dots, v_{n}\); and
• \(Ax + B\) be a linear function corresponding to \(p\).

Then,

\[ \begin{aligned} &f(S \cup \lbrace p \rbrace) - f(S) \\ &= \left\lbrack(c(A(ax+b) + B) + d)- (c(ax + b) + d)\right\rbrack_{x=0} \\ &= c((A-1)b + B) \\ &f(T \cup \lbrace p \rbrace) - f(T) = c'((A-1)b' + B).\\ \end{aligned} \]

Since \(b \leq b'\) and \(c \leq c'\), and \(A-1\) and \(B\) are both non-negative, so (the former) \(\leq\) (the latter) is asserted. Thus, the inequality in the proposition was proven. (End of proof)

Also, the following fact holds:

Let \(S\) and \(T\) be the set of problems with \(A \geq 2\); then

\[f(S) + f(T) \leq f(S \cup T) + f(S \cap T).\]

(Proof):

The equality holds if \(S=T\), so we assume \(S \neq T\).
Let \(S \cap T = U\) and \(S \setminus T = V\) (where \(\setminus\) denotes the set difference.
Then, \(U \subset T\), and \(V\) is the set of problems not contained in \(T\), so one can apply the inequality in the last proposition to show that

\[f(U \cup V) - f(U) \leq f(T \cup V) - f(T).\]

By the way, since

\[U \cup V = (S \cap T) \cup (S \setminus T) = S,\]

\[T \cup V = S \cup T,\]

one can replace \(U\) and \(V\) with \(S\) and \(T\) to obtain

\[f(S) - f(S \cap T) \leq f(S \cup T) - f(T),\]

whose transposition is what we wanted. (End of proof)

The inequalities in these two propositions are called diminishing marginal utility and submodularity (with inequality sign flipped); it seems that their equivalence are widely known in the field of combinational optimization. (It is also mentioned in Wikipedia: Link)

Mongeness and Alien DP

Now we consider the original problem. Since the problem with \(A=1\) can be solved lastly on a day, with a proper preprocess it is sufficient to solve when \(2 \leq A_i\), so we now assume that \(2 \leq A_i\).

For simplicity, we rephrase it to a shortest path problem. Define the cost \(c(u,v)\) of the directed edge from vertex \(u\) to vertex \(v\) (where \(u \lt v\)) by the cost required to solve \([u+1, v]\); then a \(K\)-day practice can be considered as a \(0-N\) path consisting of \(K\) edges on the graph \(G\) with the \((N+1)\) vertices: vertex \(0\), vertex \(1\), \(\dots\), and vertex \(N\).

Then, by the submodularity of the cost function, the edge weights evidently satisfy the following inequality:

For \(i,j,k\), and \(l\) such that \(0 \leq i \lt j \lt k \lt l \leq N\),

\[c(i, l) + c(j, k) \geq c(i, k) + c(j, l).\]

This property is called Mongeness or the quadrangle inequality (QI).

Let \(d(k)\) be the shortest length of a \(k\)-edge path \(0-N\) on a graph whose edge weights have Mongeness. Then, \(d(1), d(2), \dots\), and \(d(N)\) have the following property called convexity:

For \(2 \leq n \leq N-2\),

\[d(n) - d(n - 1) \geq d(n-1) - d(n - 2).\]

The validity is described in the following article (in Japanese). Article by noshi91

By this property, the value \(d(K)\) for a fixed \(d(K)\) can be computed with a binary search using a DP (Dynamic Programming) called Alien DP. For the details of Alien DP, please refer to the past editorial (link).

(By the way, this DP originates from an IOI (International Olympiad in Informatics) problem “Aliens”, so it may be more precise to call it “Aliens DP.” Depending on context, it is also called “wqs binary search” or “Lagrange relaxation.”)

Let’s leave it at that. This problem asks to find the minimum \(K\) such that \(d(K) \leq X\), and \(d(K)\).
If you do binary search which internally calls Alien DP, this can be solved in about \(\mathrm{O}(N \log^2 X \log N)\) time, but this probably leads to TLE (Time Limit Exceeded). (If the constant factor of your implementation is good enough, or if you do some obvious pruning, your code may be accepted.)
Such \(K\) and \(d(K)\) can be found with a trinary search. (Alternatively, we can store the counts in DP using binary search, just as explained in Alien DP, but handling contiguous segments with the same slope is a bit complicated, so it is easier to go for trinary search.)

We explain how to do trinary search. Let

• \(F(x)\): the convex function formed by connecting \((1, d(1)), (2, d(2)), \dots, (N, d(N))\);
• \(G(p)\): the maximum cost when the cost per operation is \(p\) in Alien DP.

Then, \(D\) is obviously the intersection of \(y = F(x)\) and \(y = X\), with \(x\) coordinates rounded up, but Alien DP only yields the pair \((p, G(p))\) (and the count), so it is not easy to find straightforward.
In fact, \(D\) can be found by the following procedure.

\(D\) can be represented by the following expression:

\[D = \mathrm{ceil}\left( \max_{p} \left(\frac{G(p)-X}{p}\right) \right).\]

the function \(\frac{G(p)-x}{p}\) in \(\max\) is a concave function, so \(D\) can be found by a trinary search.

The first expression can be verified by some deformation. The concavity of \(\frac{G(p)-x}{p}\) can be proved by the fact that \(F(x)\) is a convex function and the slope within the domain is always negative.

Based on the discussion so far, the problem so far has been solved by constructing an appropriate DP and performing a trinary search.

• For the DP part, one may use an even advanced algorithm (LARSCH), but one can ignore the edges with costs greater than \(X\) to construct an \(\mathrm{O}(N \log X)\) DP. (The validity is not obvious because \(F(x)\) is no longer convex, but we think that this is valid because Alien DP is an algorithm that ultimately obtains the convex hull of \(F(x)\), and even if we ignore the edges greater than \(X\), the legitimate solution can be obtained within \(y \leq X\) and \(D \leq x\).)
• Also, it is sufficient to search \(p\) less than or equal to \(X\). (\(\frac{G(p)-X}{p}\) may be at maxima at \(p\) greater than \(X\); however, in that case, \(\mathrm{ceil} (\max_p \frac{G(p)-X}{p})\) coincides with \(\mathrm{ceil}(\frac{G(X)-X}{X})\), so there is no issue.)

With an appropriate implementation, the complexity is \(\mathrm{O}(N \log^2 X)\), which is fast enough.