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