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

$\displaystyle \max_{1 \le i \le j \le N} f(i, j) \cdot \sum_{k=i}^j A[k]$ $max_{1 \leq i \leq j \leq 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_{i \le a \le b \le j} 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}$ $f (i, j) = {\begin{cases} 1 & if i \geq j \\ max_{i \leq a \leq b \leq j} f (i, a) \cdot f (a + 1, b - 1) \cdot f (b, j) & otherwise, where \sum_{k = i}^{a} A [k] = \sum_{ℓ = b}^{j} A [ℓ] \end{cases}$

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

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

Comments

There are no comments at the moment.