Subtask 1

This subtask is designed to reward superexponential brute force solutions, such as recursive backtracking or enumerating all possible sequences of cuts.

Subtask 2

The key observation is the following: suppose the chocolate bar is partitioned into sub-bars. Then there exists an optimal solution that considers only one of the sub-bars.

Thus we have reduced the problem to an interval DP problem. Define ~f(i,j)~ as the maximum tastiness Alice can achieve when considering only ~A[i\ldots j]~.

We have the following recurrence for ~f(i,j)~. $$\displaystyle \begin{align*} f(i,j) &= \begin{cases} \varnothing & \text{if }j < i \\ \max\{A[i],A[j], A[i\ldots j]\} & \text{if }j - i\leq 1 \\ \max_{i\leq k < j}\{\min\{M_1(i,j,k), M_2(i,j,k)\}, A[i\ldots k], A[k+1\ldots j], A[i\ldots j]\} &\text{otherwise} \end{cases} \end{align*}$$ where $$\displaystyle \begin{align*} M_1(i,j,k) &= \min_{i\leq\ell < k}\{\max\{f(i,\ell),f(\ell+1,k), f(k+1,j)\}\} \\ M_2(i,j,k) &= \min_{k < \ell < j}\{\max\{f(i,k), f(k+1,\ell),f(\ell+1,j)\}\} \end{align*}$$ Here, ~M_1(i,j,k)~ computes Bob's optimal response to Alice cutting ~A[i\ldots j]~ into ~A[i\ldots k]~ and ~A[k+1\ldots j]~ if he chooses to cut ~A[i\ldots k]~. In particular, if Bob cuts at index ~\ell~, then Alice will pick between the pieces that grants the maximum tastiness between ~A[i\ldots\ell], A[\ell+1\ldots k], A[k+1\ldots j]~.

Similarly, ~M_2(i,j,k)~ computes Bob's optimal response to Alice if Bob chooses to cut ~A[k+1\ldots j]~. As Bob wants to minimize Alice's tastiness, Bob will pick ~\min\{M_1(i,j,k), M_2(i,j,k)\}~.

The recurrence for ~f(i,j)~ thus takes the maximum over:

• cutting the chocolate at the index ~k~ that maximizes Bob's response ~\min\{M_1(i,j,k), M_2(i,j,k)\}~;
• cutting the chocolate and immediately eating the piece with the larger tastiness; and
• eating the whole piece;

respectively.

Naively memoizing ~f(i,j)~ and ~M(i,j,k)~ will result in an ~O(n^4)~ solution, which is sufficient to pass subtask 2.

Subtask 3

To speed up the previous solution, we will define an auxiliary array $$\displaystyle g(i,j) = \begin{cases} \varnothing & \text{if } i = j \\ \max\{A[i], A[j]\} & \text{if } i = j+1 \\ \min_{i\leq\ell < j}\{\max\{f(i,\ell), f(\ell+1,j)\}\} & \text{otherwise} \end{cases} $$ Note ~g(i,j)~ can be computed in ~O(n^3)~, assuming the values of ~f~ it depends on already calculated.

To recover ~M_1(i,j,k)~ from ~g~, note that every term we are taking the minimum over in ~M_1~ is at least ~f(k+1,j)~. Thus ~M(i,j,k)\geq f(k+1,j)~. Equality holds iff any term we take the minimum over equals ~f(k+1,j)~, i.e. if ~\max\{f(i,\ell),f(\ell+1,j)\}\leq f(k+1,j)~ for any ~i\leq\ell < j~.

Thus we obtain ~M_1(i,j,k) = \max\{g(i,k), f(k+1,j)\}~, and similarly, ~M_2(i,j,k) = \max\{f(i,k), g(k+1,j)\}~, which can be computed in ~O(1)~ time.

Thus ~f(i,j)~ can be computed in ~O(n^3)~ time.