Internet Problem Solving Contest

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: g0(w)=w and gk+1(w)=g(gk(w)). Clearly if w is code of a 0-th generation plant then gk(w) is code of a k-th generation plant.

A simple way to solve this problem would be to compute the value of gK(w0) 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:w0", 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 Ci(a) – the center of mass of plant with code gi(a), Di(a) – the end-point of plant with code gi(a), wi(a) – the weight of plant with code gi(a), alphai(a) – the growth-direction at the end of plant with code gi(a) and qi(a) – the growth-unit at end of plant with code gi(a). Clearly the solution to this task is the value of CK+1(Z).

Suppose that g(a)=a1a2...an. We can derive that gi+1(a) = g(gi(a)) = gi(g(a)) = gi(a1a2...an) = gi(a1)gi(a2)...gi(an). This means that plant with code gi+1(a) consists of (possibly resized, moved and rotated) plants with codes gi(a1), gi(a2), ..., gi(an). Using the values of Ci(aj), Di(aj), wi(aj), alphai(aj), qi(aj) for each j we can easily compute the values of Ci(a), Di(a), wi(a), alphai(a), qi(a)

Using the above idea we can compute the value of CK+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.