Problem Statement
Given two integer arrays A and B of size N and M respectively. You begin with a score of 0. You want to perform exactly K operations. On the iᵗʰ operation (1-indexed), you will:
- Choose one integer
xfrom either the start or the end of any one array,AorB. Remove it from that array - Add
xto score.
Return the maximum score after performing K operations.
Example
Input:
A = [3,1,2],B = [2,8,1,9]andK=5
Output:24Explanation: An optimal solution is as follows:
- Choose from end of
B, add 9 to score. Remove 9 fromB- Choose from start of
A, add 3 to score. Remove 3 fromA- Choose from start of
B, add 2 to score. Remove 2 fromB- Choose from start of
B, add 8 to score. Remove 8 fromB- Choose from end of
A, add 2 to score. Remove 2 fromAThe total score is
9 3 2 8 2 = 24
Constraints
- 1 ≤
N≤ 6000 - 1 ≤
M≤ 6000 - 1 ≤
A[i]≤ 109 - 1 ≤
B[i]≤ 109 - 1 ≤
K≤NM
My Approach
Since, greedy [choosing maximum end from both array] approach is failing here [because it will produce conflict when maximum end of both array is same], it suggests we have to look for all possible combinations. There will be overlapping sub-problems, hence DP!
Here is the python reprex code for the same.
A = [3,1,2]
N = len(A)
B = [2,8,1,9]
M = len(B)
K = 5
memo = {}
def solve(i,j, AL, BL):
if (i,j,AL,BL) in memo:
return memo[(i,j,AL,BL)]
AR = (N-1)-(i-AL)
BR = (M-1)-(j-BL)
if AL>AR or BL>BR or i j==K:
return 0
op1 = A[AL] solve(i 1,j,AL 1,BL)
op2 = B[BL] solve(i,j 1,AL,BL 1)
op3 = A[AR] solve(i 1,j,AL,BL)
op4 = B[BR] solve(i,j 1,AL,BL)
memo[(i,j,AL,BL)] = max(op1,op2,op3,op4)
return memo[(i,j,AL,BL)]
print(solve(0,0,0,0))
In brief,
iindicates that we have performedioperations fromAjindicates that we have performedjoperations fromB- Total operation is thus
i j ALindicates index on left of which which all integers ofAare used. SimilarlyARindicates index on right of which all integers ofAused for operation.BLindicates index on left of which which all integers ofBare used. SimilarlyBRindicates index on right of which all integers ofBused for operation.
We are trying out all possible combination, and choosing maximum from them in each step. Also memoizing our answer.
Doubt
The code worked fine for several test cases, but also failed for few. The message was Wrong Answer means there was no Time Limit Exceed, Memory Limit Exceed, Syntax Error or Run Time Error. This means there is some logical error only.
Can anyone help in identifying those Test Cases? And, also in understanding intuition/reason behind why this approach failed in some case?
CodePudding user response：
Examples were posted code gives the wrong answer:
Example 1.
A = [1, 1, 1]
N = len(A)
B = [1, 1]
M = len(B)
K = 5
print(print(solve(0,0,0,0))) # Output: 4 (which is incorrect)
# Correct answer is 5
Example 2.
A = [1, 1]
B = [1]
N = len(A)
M = len(B)
K = 3
print(print(solve(0,0,0,0))) # Output: 2 (which is incorrect)
# Correct answer is 3
Alternative Code
def solve(A, B, k):
def solve_(a_left, a_right, b_left, b_right, remaining_ops, sum_):
'''
a_left - left pointer into A
a_right - right pointer in A
b_left - left pointer into B
b_right - right pointer into B
remaining_ops - remaining operations
sum_ - sum from previous operations
'''
if remaining_ops == 0:
return sum_ # out of operations
if a_left > a_right and b_left > b_right:
return sum_ # both left and right are empty
if (a_left, a_right, b_left, b_right) in cache:
return cache[(a_left, a_right, b_left, b_right)]
max_ = sum_ # init to current sum
if a_left <= a_right: # A not empty
max_ = max(max_,
solve_(a_left 1, a_right, b_left, b_right, remaining_ops - 1, sum_ A[a_left]), # Draw from left of A
solve_(a_left, a_right - 1, b_left, b_right, remaining_ops - 1, sum_ A[a_right])) # Draw from right of A
if b_left <= b_right: # B not empty
max_ = max(max_,
solve_(a_left, a_right, b_left 1, b_right, remaining_ops - 1, sum_ B[b_left]), # Draw from left of B
solve_(a_left, a_right, b_left, b_right - 1, remaining_ops - 1, sum_ B[b_right])) # Draw from right of B
cache[(a_left, a_right, b_left, b_right)] = max_ # update cache
return cache[(a_left, a_right, b_left, b_right)]
cache = {}
return solve_(0, len(A) - 1, 0, len(B) - 1, k, 0)
Tests
print(solve([3,1,2], [2,8,1,9], 5) # Output 24
print(solve([1, 1, 1], [1, 1, 1], 5) # Output 5
CodePudding user response：
The approach is failing because the Recursive Functions stops computing further sub-problems when either "AL exceeds AR" or "BL exceeds BR".
We should stop computing and
return 0only when both of them are True. If either of "ALexceedsAR" or "BLexceedsBR" evaluates to False, means we can solve that sub-problem.
Moreover, one quick optimization here is that when N M==K, in this case we can get maximum score by choosing all elements from both the arrays.
Here is the correct code!
A = [3,1,2]
B = [2,8,1,9]
K = 5
N, M = len(A), len(B)
memo = {}
def solve(i,j, AL, BL):
if (i,j,AL,BL) in memo:
return memo[(i,j,AL,BL)]
AR = (N-1)-(i-AL)
BR = (M-1)-(j-BL)
if i j==K or (AL>AR and BL>BR):
return 0
ans = -float('inf')
if AL<=AR:
ans = max(A[AL] solve(i 1,j,AL 1,BL),A[AR] solve(i 1,j,AL,BL),ans)
if BL<=BR:
ans = max(B[BL] solve(i,j 1,AL,BL 1),B[BR] solve(i,j 1,AL,BL),ans)
memo[(i,j,AL,BL)] = ans
return memo[(i,j,AL,BL)]
if N M==K:
print(sum(A) sum(B))
else:
print(solve(0,0,0,0))
[This answer was published taking help from DarryIG's Answer. The reason for publishing answer is to write code similar to code in question body. DarryIG's answer used different prototype for function]