thedark's blog

HourRank Problem B
By thedark, history, 7 years ago, In English

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.

  • Vote: I like it
  • +10
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you please elaborate on the generator matrix for exponentiation

    → Reply
»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply