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

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

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 ?

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

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

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.

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

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

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

      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]

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

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