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 1 to N, with riceball i having size A[i]. Define a boolean function f(i, j) to return 1 if the riceballs in the range [i, j] can all be combined into a single riceball, or 0 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]

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_{l=b}^{j} A[l]

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

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


There are no comments at the moment.