Editorial for CCC '16 S4 - Combining Riceballs


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: FatalEagle

Suppose the riceballs are numbered from 11 to NN, with riceball ii having size A[i]A[i]. Define a boolean function f(i, j)f(i, j) to return 11 if the riceballs in the range [i, j][i, j] can all be combined into a single riceball, or 00 otherwise. The final answer to the problem is:

\displaystyle \max_{i=1}^N \max_{j=i}^N f(i, j) \cdot \sum_{k=i}^j A[k]\displaystyle \max_{i=1}^N \max_{j=i}^N f(i, j) \cdot \sum_{k=i}^j A[k]

Remember that no matter how you combine riceballs in an interval, after they are combined the size will always be the same.

We have the following recurrence:

\displaystyle f(i, j) = \begin{cases}
1 & \text{if } i \ge j \\
\max f(i, a) \cdot f(a+1, b-1) \cdot f(b, j) & \text{otherwise, where } \sum_{k=i}^a A[k] = \sum_{\ell=b}^j A[\ell]
\end{cases}\displaystyle f(i, j) = \begin{cases}
1 & \text{if } i \ge j \\
\max f(i, a) \cdot f(a+1, b-1) \cdot f(b, j) & \text{otherwise, where } \sum_{k=i}^a A[k] = \sum_{\ell=b}^j A[\ell]
\end{cases}

To speed this up, notice that for every aa there is at most one bb that satisfies the size restriction, and when aa increases, bb decreases, so all valid pairs may be found with a two-pointers algorithm.

Complexity: \mathcal{O}(N^3)\mathcal{O}(N^3)


Comments

There are no comments at the moment.