The first problem I will be discussing here, is "Plant", where a group of dwarves planted a very interesting recursive plant!! (Maybe the dream of any housewife? :p )
- Solution's "entangled" recursive behaviour
More formally, we have a triangle, that on each new year is filled with one triangle on its inside, according to the following rules:
If the triangle is pointing up, it's filled with one triangle pointing down, now having 3 smaller triangles upwards and one triangle downwards.
If the triangle is pointing down, it is filled with one triangle pointing up, now having 3 smaller triangles downwards and one triangle upwards.
These two rules will be the basis to build our solution.
Let's denote as f(U, n) the number of upwards and downwards triangles that will be generated, if starting from year n with an upwards triangle and similarly f(D,n) the number of upwards and downwards triangles generated if we start on year n, with a downwards triangle.
We now see that, if we start on year 1, with both an upwards triangle and a downwards triangle, we will get:
obviously, by this notation, the answer to the original problem will be f(U,n-1) (we start on year n-1, and finish at year n, and will only count the number of upwards triangles there)
- Assembling the matrix and understanding the exponentiation
So, as we can see there's more to this problem than a simple recursive relationship, as the number of up and down triangles after n years will depend on eachother's values. Fortunately, we have a very powerful tool on our arsenal as programmers which is matrix manipulation and more specifically, matrix exponentiation.
As we identified the need of using a matrix to modelate our system initial state, it follows naturally that matrices will need to be used to simulate the evolution (on this case the plant growth rate) of it as well.
Our matrix can be assembled by merging the numbers highlighted in red above, so:
will be the matrix that will model our system and allow us to get a solution, as now it's only a matter of computing the Nth power of this matrix to obtain the answer!!
- Implementation of the idea on a programming language
To implement our idea, we now need to apply any algorithm we know of that does matrix exponentiantion, but, for n as large as 1000000000000000000, a naive exponentiation algorithm won't run in time, and the trick is to use the generalized form of exponentiation by squaring applied to matrices, which can be seen here (more information about the original method extended with modular exponentiation can be found on "Introduction to Algorithms" by Cormen, Leiserson, Rivest & Stein, p.879, Chapter 31, 2nd edition).
Now, to show the implementation, I decided to use Python, as there was an already coded fast exponentiantion algorithm on a GCJ editorial (Round1A 2008), and also, because I think that the Python code is more readable and more suitable for tutorial purposes:
- Final remarks
My next goal now, is to be able to replicate this code on C++, in order to get better and better!!
Also, this was my first "editorial" here, I am not sure if you liked it, if it was too long, confuse, etc, etc, but as this is a work in progress any critics and new ideas for future posts will be welcome!
Best regards,
Bruno
Very nice analysis! However, I think that introducing matrix exponentiation is unnecessary for this task, since we have a rather simple system of recurrence relations here, we can relatively easily reduce it to integer exponentiation:
Let's take two sequences, A and B, where A will be the sequence of amounts of upwards triangles, and B the sequence of downwards ones. We know the following:
A[0] = 1 B[0] = 0
A[i] = A[i-1] * 3 + B[i-1] (i > 0) (F1) B[i] = A[i-1] + B[i-1] * 3 (i > 0) (F2)
Solving the following recurrence system easily yields a 2nd order homogeneous difference equation:
3 * A[i] — B[i] = 8 * A[i-1] (3*F1 — F2)
3 * A[i] = 8 * A[i-1] + Bi
3 * A[i-1] = 8 * A[i-2] + B[i-1] (F3 for i-1)
A[i] — 3 * A[i-1] = 3 * A[i-1] + B[i-1] — 8*A[i-2] — B[i-1] (F1 — F3)
A[i+2] = 6 * A[i+1] — 8 * A[i]
Solving this yields A[i] = 2^(i-1) * (2^i + 1). Now all we got to do is calculate 2^(n-1) and 2^n to solve the task. Do mind the special case when n = 0 though, i forgot that one at the contest and got hacked :P
There are other, less formal ways of deducing this A[i] formula. For example, one may notice that the number of upwards triangles will always be 1 + 2 + ... + 2^N (if we observe them by "rows"). This gives us (using the formula for the sum of first K numbers):
2^N*(2^N + 1) / 2 = 2^(N-1) * (2^N + 1)