unt311's blog

visualizing dp states of the question Multiplicity
By unt311, history, 4 years ago, In English

I've been trying to do this question since many hours and am unable to visualize the authors solution. The question involves maintaining a 1d dp from a 2d dp.

I'm unable to understand what does dp[j] represent in the authors solution after ignoring (i) from dp states ?

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

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

It's not a very clear tutorial, in fairness.

The idea is that you have an array of counts (cnt in the author's solution), which after 0 indices has cnt[0] = 1, and cnt[x] = 0 for all other x (up to 10^6). You iterate through each index of the array a, and update the cnt array each time (this is like the first dimension of the DP, except that you aren't storing all the old cnt arrays, you're just updating the new one, to avoid MLE). The second dimension of the DP is handled by looking at all the factors of a[i], and these are stored in a temporary vector (cur). At the end of each iteration, cur is used to update all of the indices of cnt which could possibly have changed, thus avoiding iterating through every index and risking a TLE.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    while updating the dp[j] why do we need to iterate through the divisors(j) in the descending order?

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

      The reason for that is that when we have a factor j, and we need to update cnt[j], we must add to j the value of cnt[j-1] from the previous iteration since we effectively want to do dp[i][j] += dp[i-1][j-1]. By iterating in descending order, we ensure that we have dp[i-1][j-1], not dp[i][j]

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

The basic idea is that $$$dp_{i}$$$ = # of good subsequences of length $$$i$$$. Then you can iterate through the array, find all of the divisors of $$$a[i]$$$ and then update the answer accordingly. Don't forget to increase $$$dp[1]$$$ after each iteration! My code: https://codeforces.net/contest/1061/submission/104371163

→ Reply