### grapo_Oranges's blog

By grapo_Oranges, history, 13 months ago,

This Problem was given by DeadlyCritic as a challenge

###### Statement:

Given 1369D - TediousLee solve it for $10^{18}$ without using Matrix Exponentiation.

###### Solution:

In order to maximize the number of Claws, the basic idea is to keep track of $no. of$ $nodes$ with no child at any $k^{th}$ $level$. So, max no of nodes that can be painted yellow for any $nth$ level is given by:

$$\operatorname{sum}=4 *\left(\sum_{i=0}^{\left(\frac{n-2}{3}\right)} a_{((n-2) \% 3+3 i)}\right)$$

where, $a_{i}=$ no of nodes with no child at $i^{th}$ level

Now in order to get $a_{i}$ we use this recurrence: $$f(x)=2 * f(x-2)+f(x-1)$$

Linear recurrence like this can be solve using characteristic equation, i will not get into details for the sake of keeping this blog short! Here is the equation:

$$\begin{array}{c} f(x)-2 * f(x-2)-f(x-1)=0 \\ r^{n}-2 * r^{n-2}-r^{n-1}=0 \\ r^{n-2}\left(r^{2}-2-r\right)=0 \end{array}$$

From above, quadratic equation has two distinct solutions $r1 = 2$, $r2 = -1$

Now, $$a_{n}=\alpha r_{1}^{n}+\beta r_{2}^{n}$$ is the general term of the series we build from recurrence and, $$\alpha=\frac{1}{3} \text { and } \beta=-\frac{1}{3}$$ that can be easily found using initial conditions i.e. $a_{0} = 0$ & $a_{1} = 1$

Till now, $$a_{n}=\frac{1}{3} *(2)^{n}-\frac{1}{3} *(-1)^{n}$$ Finally, we have deduced the summation into a nice formula using geometric series $$\operatorname{sum}=4 * \frac{1}{3} *\left(2^{(x \% 3)} *\left(\frac{8^{\left(\left|\frac{x}{3}\right|+1\right)}-1}{7}\right)-(-1)^{(x \% 3)} *\left(\frac{1-(-1)^{\left(\left|\frac{x}{3}\right|+1\right)}}{2}\right)\right)$$

where $x = n - 2$

Although, there can be many questions related to each step, but I'll leave that upon reader to think, all I wanted is to give a basic idea on how to solve this type of recurrence. Feel free to correct any errors. It was nice experience to write my first blog :)

My Submission : 84891174

• +142

 » 13 months ago, # |   +1 Auto comment: topic has been updated by grapo_Oranges (previous revision, new revision, compare).
 » 13 months ago, # | ← Rev. 2 →   0 can you explain the formula of the summation of the number of claws why is it so ?
 » 13 months ago, # |   +17 Nice, I didn't verify the equations and formulas, but it was the same as I did. You could check OEIS to get the general term of $f_i = f_{i-1} + 2 \cdot f_{i-2}$.
•  » » 13 months ago, # ^ |   +3 Thanks, it was great fun to solve your challenge version of this problem $:)$