## IPSC 2006

## Solution to Problem F – Fractal Plants

At first, some notations. Let **g** be the function that translates
a genetic code to the code for the next generation.
Next we define the iteration of function **g**: **g**^{0}(w)=w and **g**^{k+1}(w)=g(g^{k}(w)).
Clearly if **w** is code of a 0-th generation plant then **g**^{k}(w) is code of a **k**-th generation plant.

A simple way to solve this problem would be to compute the value of **g**^{K}(w_{0}) to get the code
of **K**-th generation plant, interpret it to get the shape of that plant (it is a polyline) and
find its center of mass.
This aproach is simple, but it is very memory and time consuming. We need something more efficient.

To make things simpler we add the rule "**Z:w**_{0}", where the letter **Z** does not occur in the input.
For each letter **a** and each integer **i** such that **0≤i≤ K+1** we compute the values
**C**^{i}(a) – the center of mass of plant with code **g**^{i}(a),
**D**^{i}(a) – the end-point of plant with code **g**^{i}(a),
**w**^{i}(a) – the weight of plant with code **g**^{i}(a),
**alpha**^{i}(a) – the growth-direction at the end of plant with code **g**^{i}(a) and
**q**^{i}(a) – the growth-unit at end of plant with code **g**^{i}(a).
Clearly the solution to this task is the value of **C**^{K+1}(Z).

Suppose that **g(a)=a**_{1}a_{2}...a_{n}. We can derive that
**g**^{i+1}(a) = g(g^{i}(a)) = g^{i}(g(a)) = g^{i}(a_{1}a_{2}...a_{n})
= g^{i}(a_{1})g^{i}(a_{2})...g^{i}(a_{n}).
This means that plant with code **g**^{i+1}(a) consists of (possibly resized, moved and rotated) plants
with codes **g**^{i}(a_{1}), **g**^{i}(a_{2}), ..., **g**^{i}(a_{n}).
Using the values of **C**^{i}(a_{j}), **D**^{i}(a_{j}),
**w**^{i}(a_{j}), **alpha**^{i}(a_{j}), **q**^{i}(a_{j})
for each **j** we can easily compute the values of **C**^{i}(a), **D**^{i}(a),
**w**^{i}(a), **alpha**^{i}(a), **q**^{i}(a)

Using the above idea we can compute the value of **C**^{K+1}(Z) by the way of dynamic programming.
Space complexity of this algorithm is linear w.r.t. input size and time complexity of it is **O(K*|g|)**,
where **|g|** is size of description of function **g**.