[Python3] Optimised knapsack DP with sliding window, <1s (faster than 100% at time of writing)
Note that this is intended to explain additional optimisations to the knapsack DP with sliding window solution method given in other solutions (e.g. lee215), wh
Note that this is intended to explain additional optimisations to the knapsack DP with sliding window solution method given in other solutions (e.g. lee215), which is not itself explained in detail here (although the code is commented with rationale behind individual steps). I would therefore recommend looking at other solutions first and then returning if you do not follow the general solution method.\n\nPlease comment below if you do not find this satisfactory and you would like me to include a more in-depth explanation of the general method.\n\n# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThis was an interesting problem that needed to be tackled in a specific way (i.e. using sliding window with DP) in order to achieve the requisite execution speed. However, even after solving in a way that passed all the required time, there were still further optimisations which, although not influencing the time or space complexity, could eliminate unnecessary calculations and so speed up the evaluation time. The main 2 were:\n\n- For a given index i strictly less than l, stopping the calculation of the DP array once the value at this index no longer influences the DP array values of interest (i.e. from l to r inclusive).\nFor example, say $$l = 100$$ and we are on the penultimate iteration and the final iteration will address the number $$6$$ with a frequency of $$2$$. Consider an index $$i < 100 - 2 * 6 = 88$$. In the final iteration, the largest index of the final DP array this can influence is $$i + 2 * 6 < l$$, so it does not influence the final result. Therefore, for the current iteration, the result will remain unchanged if the DP array values with indices less than $$88$$ are not updated. This can cut down a lot of unnecessary calculation, at least for later iterations and large $$l$$.\nThis appears to contribute a reduction in time of a factor of approximately 1.5\n- Instead of for every step of the process updating all indices up to r, not iterating beyond the largest index that can be changed.\nFor example, say we have a situation where $$r = 1000$$, and we are in the first iteration (so all elements of the DP array are $$0$$ except for at index $$0$$, which is $$1$$) and number addressed in this iteration $$2$$ which has a frequency of $$3$$. Given that the largest index in the DP array with non-zero value is $$0$$ and the largest contribution that can be made by $$2$$s in terms of the multiset sum is $$2 * 3 = 6$$, the largest index of the DP array whose value can (and indeed will) be changed during this itereration is $$0 + 6 = 6$$. It is therefore unnecessary to perform the calculations for indices between $$7$$ and $$r = 1000$$. This can also cut down a lot of unnecessary calculation, at least for early iterations.\nThis appears to contribute a reduction in time of a factor of approximately 2.\n\nAdditionally, by iterating over the numbers in ascending order of size turned out to be marginally faster than from descending order of size, though this is empirical and I do not at present have an intuitive explanation as to why that should be the case.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nThe general approach is similar to most other solutions (e.g. lee215- see these and the comments in the code below for a more detailed explanation), incorporating the above optimisations which collectively contributed a reduction in execution time of approximately 3.\n\n# Complexity\nWith $$n = len(nums)$$ and $$m$$ as the number of distinct elements of $$nums$$ (which itself is $$O(\\sqrt{n})$$):\n\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n$$O(nm)$$ or, in terms of just the explicitly restricted parameters, $$O(n^{3 / 2})$$\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n$$O(r + m)$$ or, in terms of just the explicitly restricted parameters, $$O(r + \\sqrt{n})$$\n\n# Code\n```\nclass Solution:\n    def countSubMultisets(self, nums: List[int], l: int, r: int) -> int:\n        md = 10 ** 9 + 7\n        dp = [0] * (r + 1)\n        dp[0] = 1\n        mx_nonzero = 0\n        f_dict = Counter(nums)\n        nums2 = sorted(f_dict.keys(), reverse=True)\n        if not nums2[-1]: nums2.pop()\n        n = len(nums2)\n        cumu_rev = sum(x * f_dict[x] for x in nums2)\n        for idx in reversed(range(n)):\n            num = nums2[idx]\n            # The largest possible collective contribution from the\n            # iterations after this one to any multiset sum\n            cumu_rev -= num * f_dict[num]\n            # The smallest index in the DP array that can influence\n            # the final result (and so the smallest index that needs\n            # to be updated)\n            mn = max(0, l - cumu_rev)\n            # The largest index in the DP that can be non-zero after\n            # the current iteration\n            mx_nonzero = min(r, mx_nonzero + num * f_dict[num])\n            # Iterating over different congruences modulo num of the\n            # endpoints of the sliding windows (which themselves slide\n            # by increments of num to the left, thus requiring up to\n            # num sliding windows for complete coverage)\n            for i1 in reversed(range(max(mx_nonzero - num + 1, mn), mx_nonzero + 1)):\n                # The largest frequency of num that can appear in a\n                # multiset with sum i1\n                f0 = min(f_dict[num], i1 // num)\n                # The initial sum over the sliding window\n                curr = sum(dp[i1 - num * j] for j in range(1, f0 + 1)) % md\n                # The (possibly empty) range of indices (in increments of num)\n                # for which the left end of the sliding window is no less than\n                # num, and so when shifting the sliding window to the left by a\n                # displacement of num, updating the sliding window value requires\n                # adding a new value on the left end\n                i_rng1 = (i1, min(i1, max((i1 % num) + (f0 * num), max(mn, num) - 1)))\n                # The (possibly empty) range of indices (in increments of num)\n                # for which the left end of the sliding window is strictly less than\n                # num, and so when shifting the sliding window to the left by a\n                # displacement of num, updating the sliding window value does not\n                # require adding a new value on the left end\n                i_rng2 = (i_rng1[1], min(i_rng1[1], max(mn, num) - 1))\n                for i in range(*i_rng1, -num):\n                    dp[i] = (dp[i] + curr) % md\n                    curr = (curr - dp[i - num] + dp[i - (f0 + 1) * num]) % md\n                for i in range(*i_rng2, -num):\n                    dp[i] = (dp[i] + curr) % md\n                    curr = (curr - dp[i - num]) % md\n        # As adding any number of 0s to a multiset does not affect\n        # its sum, the zero count\'s net effect is to multiply the\n        # result when ignoring the zeros by the zero count plus 1\n        return ((sum(dp[l:]) % md) * (f_dict.get(0, 0) + 1)) % md\n```
['Python3']