Codeforces and Polygon may be unavailable between Aug. 17, 19:00 (UTC) to Aug. 17, 22:00 (UTC) due to planned power outages. ×

Spheniscine's blog

By Spheniscine, history, 23 months ago,

Spoiler

Spoiler

Spoiler

Spoiler

Spoiler

F – Contrast

Spoiler

• +51

 » 23 months ago, # |   0 Can you share the O(logs) solution of D.
•  » » 23 months 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$.
•  » » » 23 months ago, # ^ |   0 Cool explanation. Thanks.
 » 23 months ago, # |   0 Cool editorial.
 » 23 months ago, # |   0 I'm a simple man. I see a blog post by Spheniscine, I upvote.
 » 23 months 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?
•  » » 23 months 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.
 » 22 months ago, # |   0 For problem C, since the number of ways to put 10 numbers in $n - 2$ positions (since I locked in 2 positions for 9 and 0) is $10^{n - 2}$. Then the number of ways to permute this combination of $n$ numbers is $n!$. So my formula is $n! \cdot 10^{n-2}$. But this is wrong, why?
•  » » 18 months ago, # ^ | ← Rev. 2 →   0 Because you are overcounting situations where more than one permutation would produce the same result. You also failed to distinguish the 9 and 0 you locked in with other 9s and 0s that may be produced.One has to be careful in combinatorics problems, that the choices one could make in the construction has a one-to-one correspondence with the possible results, or that one could compensate for any overcounting / undercounting.