Блог пользователя Spheniscine

Автор Spheniscine, история, 4 года назад, По-английски

A – Not

Spoiler

B – Product Max

Spoiler

C – Ubiquity

Spoiler

D – Redistribution

Spoiler

E – Dist Max

Spoiler

F – Contrast

Spoiler
  • Проголосовать: нравится
  • +51
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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$$$.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Cool editorial.

»
4 года назад, # |
  Проголосовать: нравится 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^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?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 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.

»
4 года назад, # |
  Проголосовать: нравится 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?

  • »
    »
    4 года назад, # ^ |
    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.