### Spheniscine's blog

By Spheniscine, history, 12 days ago,

Spoiler

Spoiler

Spoiler

Spoiler

Spoiler

### F – Contrast

Spoiler

• +46

 » 12 days ago, # |   0 Can you share the O(logs) solution of D.
•  » » 12 days ago, # ^ |   +11 First prove by induction that $dp_i = dp_{i-3} + dp_{i-1}$ for all $i \ge 3$:It can be seen to be true for $dp_3$. Now assuming that $dp_i = dp_{i-3} + dp_{i-1}$, try to prove the relation holds for $dp_{i+1}$.$dp_{i+1} = \sum_{j=0}^{i-2} dp_j = dp_{i-2} + \sum_{j=0}^{i-3} dp_j = dp_{i-2} + dp_i$, Q.E.D.Now construct the matrix for the transition function $F(dp_i, dp_{i+1}, dp_{i+2}) = (dp_{i+1}, dp_{i+2}, dp_{i+3})$.$F(a, b, c) = (b, c, a+c)$, thus in matrix form $F = \begin{bmatrix} 0&1&0 \\ 0&0&1 \\ 1&0&1 \end{bmatrix}$. Let vector $V = \begin{bmatrix} dp_0 \\ dp_1 \\ dp_2 \end{bmatrix} = \begin{bmatrix} 1 \\ 0 \\ 0 \end{bmatrix}$. Compute $F^sV$ and take the first value of the resulting vector, that's $dp_s$.
•  » » » 12 days ago, # ^ |   0 Cool explanation. Thanks.
 » 12 days ago, # |   0 Cool editorial.
 » 12 days ago, # |   0 I'm a simple man. I see a blog post by spheniscine, I upvote.
 » 9 days ago, # |   0 For C,I thought a sequence that has at least one 9 will be 10^(n-1). Similarly for 0 also 10^(n-1). if we add both these we will be adding two times the common part which has both 9 and 0. so we will subtract it once.Total Sequences = 10^nSequences which don't have either 9 or 0 = 8^nFinal Equation10^n = 2*(10^(n-1)) — (Common Part) + 8^nCommon Part = 2*(10^(n-1)) — 10^n + 8^nIs this correct?
•  » » 8 days ago, # ^ |   0 No, as the position of the 9 and 0 aren't fixed.Similarly, fixing the 9 and 0 before filling the rest won't work because the other numbers could be 9 or 0 as well.