Editorial for BSSPC '22 P5 - Derrick and Orz Trees


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

Subtask 1

Note that the trees are independent, and can be considered individually.

As such, the question is: how many gardens can a single tree produce?

For each tree, if it's odd we can't do anything. If it's even, we can either not cut it, or cut it into two halves, each of which we should consider separately. Mathematically:

f(h)=f(h2)f(h2)+1

Implementing this as above yields O(i=1NHi). Proof is left as an exercise to the reader. Don't forget to mod.

Subtask 2

We can do:

f(h)=f(h2)2+1

instead. This gives us O(NlogHi).

Informal Proof

Suppose we have a garden G produced from H. We can show that this garden can only be produced in one way.

In particular, consider the prefix of G that sums to H1. There must be such a prefix, and furthermore, there is exactly one such prefix.

This prefix must have been created by cutting down H1, and can not have been created in any other way.

Applying this logic recursively yields our proof.


Comments

There are no comments at the moment.