Crunchy

We are given a small Python program which computes the flag:

def crunchy(n):
    if n < 2: return n
    return 6 * crunchy(n - 1) + crunchy(n - 2)
    
g = ...  # a _really_ big number
print("Your flag is: INSA{%d}"%(crunchy(g)%100000007))

Running this, of course, won’t get us anywhere with the exponentially slow implementation of crunchy. A simple improvement would be to cache computed vaues of crunchy(n), but that reduces the complexity to linear, which is still not nearly enough with the hundred-digit parameter.

Since crunchy is a linear recurrence, we can compute it in logarithmic time. We can express the mapping from (c(n),c(nβˆ’1))(c(n), c(n-1)) to (c(n+1),c(n))(c(n+1), c(n)) (where cc is the function) as a matrix multiplication:

(c(n+1)c(n))=(6110)(c(n)c(nβˆ’1)) \begin{pmatrix}c(n+1)\\c(n)\end{pmatrix} = \begin{pmatrix}6&1\\1&0\end{pmatrix} \begin{pmatrix}c(n)\\c(n-1)\end{pmatrix}

If we expand the right-hand side of this equation nβˆ’1n-1 times, we will get:

(c(n+1)c(n))=(6110)n(c(1)c(0)) \begin{pmatrix}c(n+1)\\c(n)\end{pmatrix} = \begin{pmatrix}6&1\\1&0\end{pmatrix}^n \begin{pmatrix}c(1)\\c(0)\end{pmatrix}

Since we know the values of c(1)c(1) and c(0)c(0), all that remains is to compute the exponentiated matrix. We can do this in π’ͺ(logn)\mathcal{O}(\log{n}) multiplications by repeated squaring, which is completely reasonable for the input value of g (a few hundreds of multiplications).

Note that all multiplications should be done modulo 109+710^9 + 7 instead of only doing so at the end – otherwise, the intermediate values will be to large to work with (they grow exponentially).