Dp solution - thinking process and detailed proof
Intuition\n Describe your first thoughts on how to solve this problem. \nFirst thing that came to my mind afer reading the problem statement was using binary se
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nFirst thing that came to my mind afer reading the problem statement was using binary search but found a counter example shortly thereafter. Take a glance at the constraints, it is not hard to deduce that a $$O(n^2)$$ approach should be used. With this in mind, dynamic programming is the second approach I tried tackling this problem. Here not only do I provide the approach, but also explain my thinking process in order to come up with such a solution.\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Let `n` denote the length of `nums1`. If a solution exists, it can not exceed `n`.\n\n\n    <details>\n    <summary><b>Proof</b></summary>\n    \n    \n    No index should be chosen more than once. If it had been chosen twice, we could have chosen no index in its first time instead and the sum would have remained the same. As each index is chosen at most one, therefore the answer is at most `n` (if exists).\n\n    </details>\n\n2. How do we check if a solution for `x` seconds exists. Without loss of generality, let `tot` and `inc` denote the sum of `nums1` and `nums2` respectively, suppose that the 1st till `x`th index were chosen in their respective order (1st index was chosen at time 1, 2nd index was chosen at time 2, etc...), the the current sum is $$tot + inc * x - (nums1[1] + num2[1] * 1 + nums1[2] + num2[2] * 2 ... + nums1[x] + nums2[x] * x) $$. We would like to make this sum as small as possible. The first term $$tot + inc * x$$ is fixed, therefore we maximize the second term. To do so, we must carefully choose the set of x distinct elements and arrange them in an optimal order so that the sum is maximal. We don\'t know which `x` elements should be chosen yet, but for a fixed set of `x` elements, their order can easily be selected. We just need to order them in increasing order of `nums2[i]`, if there\'s a tie, we use `nums1[i]` to break it. The proof is simple, if there were two elements `i` and `j` in which `i` had been choosen earlier than `j` and `nums2[i]` > `nums2[j]`, we can always swap `i` and `j` and the sum would not decrease, hence a more optimal solution.\n    \n3. We knew how to order a fixed set of elements, but which elements should we choose ? Dynamic prograaming comes to the rescue!!. If we sort the two arrays by `nums2[i]` then the problem can be rephrased as:\n    Given two arrays nums1 and nums2. For a fixed number x, choose x elements such that the sum $$nums1[a] + nums2[a] * 1 + nums2[b] + nums2[b] * 2 + .. nums1[n] + nums2[n] * n$$ under $$ a < b < c .. < n$$. The sollution for this problem is straightforward, it is a variant of knapsack, I\'ll leave it as an exercise for you guys. \n\nAfter having got the answer for each x, for each x from 0 to n, if the value of the equation does not exceed the target, we return x as our final answer. Otherwise, no solution exists.\n\n\n# Complexity\n- Time complexity:\n$$O(n^2)$$\n- Space complexity:\n$$O(n)$$\n\n# Code\n```\nclass Solution:\n    def minimumTime(self, nums1: List[int], nums2: List[int], target: int) -> int:\n        a = sorted(zip(nums2, nums1))\n        n = len(nums1)\n        inf = 10 ** 18\n        dp = [-inf] * (n+1)\n        dp[0] = 0\n        for y, x in a:\n            for i in range(n, 0, -1):\n                dp[i] = max(dp[i], dp[i-1] + x + y * i)\n        tot = sum(nums1)\n        inc = sum(nums2)\n        for i in range(n+1):\n            if tot + inc * i - dp[i] <= target:\n                return i\n        return -1\n\n```
['Python3']