Editorial for BSSPC '22 P5 - Derrick and Orz Trees
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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:
Implementing this as above yields
Subtask 2
We can do:
instead. This gives us
Informal Proof
Suppose we have a garden
In particular, consider the prefix of
This prefix must have been created by cutting down
Applying this logic recursively yields our proof.
Comments