Recursive Solution O(n^2) beats nobody
This isn\'t an optimal solution (in particular it isn\'t space-optimal) but I think it will be helpful.\n\n# Intuition\nWe have n counters; counter i has an ini
This isn\'t an optimal solution (in particular it isn\'t space-optimal) but I think it will be helpful.\n\n# Intuition\nWe have `n` counters; counter `i` has an initial value `nums1[i]` and increases at a rate of `nums2[i]`.\n\nNote first that it is suboptimal to reset a counter (to zero) more than once, since then the first reset is wasted. Therefore, we should consider up to `n` steps at most; if we can\'t get the sum of the counters to be `x` or lower, then we will never be able to. However, it is sometimes possible to finish in `k < n` steps. \n\nWe can also reformulate the problem as a matter of achieving maximum reduction. The total sum increases by $\\sum rate_i$ with every timestep, and whenever we reset a counter $i$ at time $t_i$ we reduce the total sum by $initial_i + t_i * rate_i$. This also means if that we decide which counters we are going to reset, the optimal order is to reset the counters in increasing order of rate. That way, when $t_i$ is higher we get a greater reduction with higher $rate_i$.\n\nThe harder part is figuring out which counters we are going to reset in the first place if we are trying to finish in less than $n$ steps.\n\n# Approach\nWe try to find a recurrence which would be useful for calculating maximum reduction. Trying to calculate $M(t)$, the maximum reduction after $t$ steps, by itself, seems implausible since it\'s not obvious how $M(t)$ relates to $M(t-1)$ (or $M(t+1)$). Instead, consider the following: we try to calculate $M(t, s)$, the maximum reducton after $t$ steps and using the $s$ counters with lowest rates.\n\nThis is a bit of a leap: why the $s$ counters with lowest rates? I don\'t have a way of suggesting how you should think of this in the first place, but it\'s easy to explain afterwards: in the end we don\'t care about any value of $s$ other than $n$ anyway, and using the $s$ counters with the lowest rates makes the recurrence easy.\n\nWhen calculating $M(t, s)$, we consider two cases: either we reset the $s$th counter (1-indexed) or we didn\'t.\n* If we reset the $s$th counter, the optimal order includes resetting it at time $t$, so we can refer to $M(t-1, s-1)$ to calculate the reduction.\n* If we didn\'t reset the $s$th counter (which is only a case when $t > s$), then the reduction is the same as $M(t, s-1)$.\n\nOnce we\'ve calculated all relevant values of $M(t,s)$ we can simply look at the values of $M(t, n)$ for all $t \\in [0, n]$; if we attain enough of a reduction to get below the threshold $x$, then we are done.\n\n# Complexity\n- Time complexity: $O(n^2)$\n- Space complexity: $O(n^2)$ due to the number of cases in cache\n\nIt is possible to reduce the space usage to $O(n)$ with a bottom-up approach; $M(t,s)$ only relies on $M(t-1, s-1)$ and $M(t, s-1)$, prior values of $s$ do not need to be kept around in memory forever. Other solutions do this.\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], x: int) -> int:\n        total_initial = sum(nums1)\n        total_rate = sum(nums2)\n        n = len(nums1)\n        counters = sorted(zip(nums2, nums1))  # (rate, initial); sorted in increasing order of rate\n        \n        # Require that counters_end_idx >= t\n        @lru_cache(None)\n        def calc_max_reduction(counters_end_idx: int, t: int) -> int:\n            if t == 0:\n                return 0\n            \n            # Get the last counter (with highest rate)\n            rate, initial = counters[counters_end_idx - 1]\n\n            # This is the case where we reduce this counter at time t\n            res = calc_max_reduction(counters_end_idx - 1, t - 1) + rate * t + initial\n            \n            # This is the case where we don\'t reduce this counter at time t\n            # (Not available if items_end == n_steps since we would be forced to reduce the counter)\n            if counters_end_idx > t:\n                res = max(res, calc_max_reduction(counters_end_idx - 1, t))\n\n            return res\n\n        for t in range(0, n + 1):\n            max_reduction = calc_max_reduction(n, t)\n            if total_initial + t * total_rate - max_reduction <= x:\n                return t\n\n        return -1\n```
['Python3']