## 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:

Suppose the riceballs are numbered from to , with riceball having size . Define a boolean function to return if the riceballs in the range can all be combined into a single riceball, or otherwise. The final answer to the problem is:

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:

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

Complexity:

## Comments