Intuition, approaching, proof and code
Intuition\n\nEDITED: fix some error, add the proof of max_possible_ops.\nEDITED 2: fix error in proof of max_possible_ops\n\n## Notations\n\nLet $A$ be the orig
# Intuition\n\nEDITED: fix some error, add the proof of `max_possible_ops`.\nEDITED 2: fix error in proof of `max_possible_ops`\n\n## Notations\n\nLet $A$ be the original `nums1`, $B$ be the original `nums2`.\nSo $A_i$ is `nums1[i]`.\nLet the length of `nums1` be $n$.\n\n## Limit\n\nAfter $n$ seconds, a intuition is that the minimum possible sum we can get of `nums1` will not decrease. So we only consider the time $[0,n]$. The proof is at the end of the Approach section.\n\n## After k seconds\n\nAfter $k$ seconds, if we don\'t do operations, `nums1` will become this:\n\n$$\nA_0 + k \\times B_0, A_1 + k \\times B_1, ..., A_{n-1} + k \\times B_{n-1}\n$$\n\nThen we add $k$ operations now, it equivalents we pick $k$ indexes $i_0, ..., i_{k-1}$, and change the values at these indexes are\n\n$$\n0, B_{i_1}, 2B_{i_2}, 3B_{i_3}, ..., (k-1)B_{i_{k-1}}\n$$\n\nNote we can pick indexes less than $k$, that means we reset twice for a index `j`. But then we can choose the earlier reset of `j`, and replace it with the reset of another index to make the sum of `nums1` smaller. That means a $k$ indexes solution is always better.\n\nThe sum of the current `nums1` is\n\n$$\n\\sum A + k \\sum B - (kB_{i_0} + (k-1)B_{i_1} + \\cdots + B_{i_{k-1}} + A_{i_0} + A_{i_1} + \\cdots + A_{i_{k-1}})\n$$\n\nTo make this minimize, it means to make this maximize\n\n$$\nkB_{i_0} + (k-1)B_{i_1} + \\cdots + B_{i_{k-1}} + A_{i_0} + A_{i_1} + \\cdots + A_{i_{k-1}}\n$$\n\n## Conclusion\n\nIn other words, we pick $k$ elements $b_0, b_1, ..., b_{k-1}$ from $B$ and their corresponding elements in $A$: $a_0,a_1, ..., a_{k-1}$, and try to maximize this:\n\n$$\nkb_0 + a_0 + (k-1)b_1 + a_1 + \\cdots + b_{k-1} + a_{k-1}\n$$\n\n# Approach\n\nIt\'s easy. For example, if we already chosen $k$ indexes, then sort all chosen $b_i$ in decreasing order, and calculate the formula in order to maximize it.\n\nSo it means we can just sort `nums2` and run dynamic programming on it. The complexity is $O(nk)$. The cached function looks like this:\n\n```python\nminimum_sum(i, k)\n```\n\nwhere `i` is the index, `k` is the number of operations.\n\nThen we scan from `0` to `max_possible_ops`:\n\n```python\nfor k in range(0, max_possible_ops):\n    if minimum_sum(0, k) <= x:\n        return k\nreturn -1\n```\n\nWhat is `max_possible_ops`?\n\nAfter $n$ seconds, every element is reset at least once. We only consider their latest reset.\n\nSuppose after $t+1$ seconds, we have sequence $a$ that can maximize this formula:\n\n$$\na_0B_0 + a_1B_1 + \\cdots + a_{n-1}B_{n-1} + \\sum A\n$$\n\n$1 \\le a_i \\le t+1$\n\nThe same for $t$ seconds, we have sequence $b$\n\n$$\nb_0B_0 + b_1B_1 + \\cdots + b_{n-1}B_{n-1} + \\sum A\n$$\n\n$1 \\le b_i \\le t$\n\nBoth sequence have no duplicate. $a$ contains $t+1$, $b$ contains $t$ for the latest reset. And $t \\ge n$.\n\nThen the increment will be\n\n$$\n\\sum B - (a_0B_0 + a_1B_1 + \\cdots + a_{n-1}B_{n-1})\n+ (b_0B_0 + b_1B_1 + \\cdots + b_{n-1}B_{n-1})\n$$\n\nThe two expression in the parentheses were maximized. We can simply sort $B$ in decreasing order and make sequence $a$ be $t+1, t, ..., t-n+2$, and $b$ be $t, t-1, ..., t-n+1$ to achieve this.\n\nFinally,\n\n$$\n\\sum B - (a_0B_0 + a_1B_1 + \\cdots + a_{n-1}B_{n-1})\n+ (b_0B_0 + b_1B_1 + \\cdots + b_{n-1}B_{n-1})\\\\\n= 0\n$$\n\nThat means the minimum sum of `nums1` after time $n$ will not decrease, and will not change actually. So `max_possible_ops` can be $n+1$.\n\n# Complexity\n\n- Time complexity: $O(n^2)$\n- Space complexity: $O(n^2)$\n\n# Code\n\nRacket code\n\n```racket\n(define (minimum-time nums1 nums2 x)\n  (define inf #e1e10)\n  (define sum1 (list-sum nums1))\n  (define sum2 (list-sum nums2))\n  (vec! nums1 nums2)\n  (define n (alen nums1))\n  (define sorted2\n    (list->vector\n      (sort (range 0 n)\n            (\u03BB (a b)\n              (> (aref nums2 a) (aref nums2 b))))))\n\n  (define (indexof i)\n    (aref sorted2 i))\n\n  (define (minimum-sum i op)\n    (match i\n      [(== n) (if (= op 0) sum1 inf)]\n      [i (min (minimum-sum (add1 i) op)\n              (if (= op 0)\n                  inf\n                  (+ sum2\n                     (- (aref nums1 (indexof i)))\n                     (- (* op (aref nums2 (indexof i))))\n                     (minimum-sum (add1 i) (sub1 op)))))]))\n\n  (cachef! minimum-sum n (add1 n) -1)\n\n  (or (for/first ([op (in-closed-range 0 n)]\n                  #:when (<= (minimum-sum 0 op) x))\n        op)\n      -1))\n\n\n(require syntax/parse/define)\n\n(define-syntax make-array\n  (syntax-rules ()\n    [(_ n init)\n     (make-vector n init)]\n    [(_ n args ...)\n     (build-vector n (lambda _ (make-array args ...)))]))\n\n(define-syntax aref\n  (syntax-rules ()\n    [(_ arr) arr]\n    [(_ arr i args ...)\n     (aref (vector-ref arr i) args ...)]))\n\n(define-syntax aset!\n  (syntax-rules ()\n    [(_ arr i v)\n     (vector-set! arr i v)]\n    [(_ arr i args ... v)\n     (aset! (vector-ref arr i) args ... v)]))\n\n(define-syntax-rule (alen arr)\n  (vector-length arr))\n\n(define-syntax-parse-rule (cachef! fn:id args:expr ...)\n  (set! fn (cachef fn args ...)))\n\n(define-syntax-parser cachef\n  [(_ fn:id)\n   #\'(cachef-hash fn)]\n  [(_ fn:id hints:expr ... init)\n   (with-syntax ([(args ...) (generate-temporaries #\'(hints ...))])\n     #\'(let* ([cache (make-array hints ... init)]\n              [ori-fn fn])\n         (lambda (args ...)\n           (cond [(or (< args 0) ...\n                      (>= args hints) ...)\n                  (ori-fn args ...)]\n                 [else\n                  (when (equal? init (aref cache args ...))\n                    (aset! cache args ... (ori-fn args ...)))\n                  (aref cache args ...)]))))])\n\n(define (cachef-hash fn)\n  (let ([cache (make-hash)])\n    (lambda args\n      (when (not (hash-has-key? cache args))\n        (hash-set! cache args (apply fn args)))\n      (hash-ref cache args))))\n\n(define-syntax-parse-rule (vec! var:id ...)\n  (let ()\n    (vec1! var) ...))\n\n(define-syntax-parse-rule (vec1! var:id)\n  (set! var\n        (cond [(string? var) (list->vector (string->list var))]\n              [(list? var) (list->vector var)]\n              [else var])))\n\n(define (list-sum lst)\n  (foldl + 0 lst))\n\n(define in-closed-range in-inclusive-range)\n```
['Racket']