Spheniscine's blog

By Spheniscine, history, 4 days ago, In English

A – Not

Spoiler

B – Product Max

Spoiler

C – Ubiquity

Spoiler

D – Redistribution

Spoiler

E – Dist Max

Spoiler

F – Contrast

Spoiler
 
 
 
 
  • Vote: I like it
  • +46
  • Vote: I do not like it

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you share the O(logs) solution of D.

  • »
    »
    4 days ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    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$$$.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

Cool editorial.

»
4 days ago, # |
  Vote: I like it 0 Vote: I do not like it

I'm a simple man. I see a blog post by spheniscine, I upvote.

»
25 hours ago, # |
  Vote: I like it 0 Vote: I do not like it

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^n

Sequences which don't have either 9 or 0 = 8^n

Final Equation

10^n = 2*(10^(n-1)) — (Common Part) + 8^n

Common Part = 2*(10^(n-1)) — 10^n + 8^n

Is this correct?

  • »
    »
    2 hours ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.