Solving D.TediousLee Using Recurrence in O(log n)

Revision en3, by grapo_Oranges, 2020-06-24 22:37:40

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:

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

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

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

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{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}\end{equation}

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

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

Till now, \begin{equation}a_{n}=\frac{1}{3} *(2)^{n}-\frac{1}{3} *(-1)^{n}\end{equation} Finally, we have deduced the summation into a nice formula using geometric series \begin{equation}\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)\end{equation}

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 to is give the 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

Tags math, sequences and series

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English grapo_Oranges 2020-06-24 22:56:55 4
en5 English grapo_Oranges 2020-06-24 22:48:03 2
en4 English grapo_Oranges 2020-06-24 22:43:40 10
en3 English grapo_Oranges 2020-06-24 22:37:40 41 (published)
en2 English grapo_Oranges 2020-06-24 22:33:33 1829 Tiny change: ' track of _no. of nodes_ with no c' -> ' track of $no. of nodes$ with no c'
en1 English grapo_Oranges 2020-06-24 21:13:57 373 Initial revision (saved to drafts)