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

HourRank Problem B
Автор thedark, история, 7 лет назад, По-английски

Could someone explain in detail how to solve this problem. The editorialist talks about matrix exponentiation. I know how to apply this when we solve linear equation, like F(N) for fibonacci series. But here we want to apply it on dp[i][j] where dp[i][j] = number of lists whose sum is i and last number is j. How we solve it.

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

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

Auto comment: topic has been updated by thedark (previous revision, new revision, compare).

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

Let DP(S, x) denote the number of lists with sum S and last element x.

Note that DP(S, x) depends on DP(S-x, y), where abs(x-y) <= d.

For calculating DP(S, x), Keep a m*m matrix consisting of combinations of DP(S2, y), where S-m <= S2 <= S-1 and 1 <= y <= m. Fill the entries of the transition matrix based on allowed transitions (i.e. abs(x-y) <= d).

Time complexity is O(m^6 * log(S)).

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you elaborate, I mean in steps how is it being carried out.

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Create an initial vector of length m*m containing the result for the first m values of s. Eg. for m = 3 it would be

      F0 = [dp[0][0], dp[0][1], dp[0][2], dp[1][0], dp[1][1], dp[1][2], dp[2][0], dp[2][1], dp[2][2] ]

      Now we need to build a m*m by m*m matrix that transitions to the vector

      F1 = [dp[1][0], dp[1][1], dp[1][2], dp[2][0], dp[2][1], dp[2][2], dp[3][0], dp[3][1], dp[3][2]]

      The first (m-1)*m rows will have just a single 1 to effectively "shift" the last (m-1)*m entries of F0 to the first (m-1)*m entries of F1. The last m rows of the transition matrix will have some ones to implement the dp formula (note that it will depend on the value of d).

      → Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Could you please elaborate on the generator matrix for exponentiation

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

I didn't know it was solvable by matrix exponentiation, I just coded a divide and conquer approach. My idea was setting the limits on the leftmost and rightmost number (for example if before the leftmost number there was a 4 and d = 2 then the limits were from 2 to 6) and choose the middle number, and then divide and conquer. When s <= 30 just tried all possible numbers for the leftmost until s = 0. All of this with memoization.

→ Ответить