Two new shops are opening inside a new building and k kinds of items are needed to stock shelves at each store. Given the prices of n items in two shops, choose exactly k indices in such a way that the minimum sum of arrays firstShop and secondShop over these indices is maximum.
Specifically, choose exactly k indices (i[1], i[2],...., i[k]) such that the value min(a[i[1]]+a[i[2]]+.... + a[i[k]], b1+b[i[2]]+...+b[i[k]]) is maximized. Find this maximum value.
Example:-
n=5, k=3
firstShop=[6, 3, 6, 5, 1]
secondShop = [1, 4, 5, 9, 2]
Choose the subset of indices as (0, 2, 3).
The value is min(6+6+5, 1+5+9)= 15, which is the maximum possible. Return 15 as the answer
1<=N,array-values<=50
My DP Solution :- O(N*K*|sum1|*|sum2|) ; where sum1 = total sum of first array ; sum2 = total sum of second array but it TLE's how to optimize?
dp[i][k][sum1][sum2] = returns true if it is possible to select k indices from (0....i) such that array1 has sum1 and array2 has sum2.
Instead of keeping track of sum1 and sum2 separately only keep track of the difference, since this is enough to determine the proper strategy.
For example, define dp[n'][k'][diff] as the best possible result if you choose k' indices from the first n', and currently sum1 = diff, sum2 = 0.
Then the recurrence is:
The first term is if you don't choose index n', the second is if you choose it.
Pls teach how to notice such recursive methods. I've learned to picture as a tree, but that never works for me.
Why are you adding min(a[i], b[i]) in diff ?
Sorry, it is a mistake. The i should be n' and that should just be b[i]. I was editing my expression and didn't pay close attention.
The reason is: If you choose index n', then you have to choose k'-1 indices from the first n'-1, and currently sum1 = a[n'] and sum2 = b[n'].
But only the difference in sum1 and sum2 matter, so the best possible result is b[n'] plus the result if you start with sum1 = a[n']-b[n'] and sum2 = 0.
Can you elaborate how dp[n][k][diff] helps in finding final answer ; sum1,sum2 actually tells us they are possible and we take their min for all possible sum1,sum2 and finally print max of all of them how is it possible in dp[n][k][diff]?
The final answer should be dp[n][k][0], because you need to choose k indices from the first n, and you start with sum1 = 0, sum2 = 0.
dp[n][k][0] means best answer such that sum1 = sum2 that is not the requirement of the problem. sum1 and sum2 can be different
Am I getting something wrong please clarify and thanks for your precious time!
No, dp[n'][k'][diff] means best answer such that you start with sum1 = diff, sum2 = 0, and then try to maximize min(sum1, sum2) by choosing k' indices from the first n'.
So in the example you gave, dp[2][1][-3] = 1. Why? Because if we start with sum1 = -3, sum2 = 0, and can choose 1 of the first 2 indices, the best thing to do is to choose the first index. Then sum1 = 3, sum2= 1, and our result will be 1.
Similarly, dp[2][1][7] = 4. If we start with sum1 = 7, sum2 = 0, the best is to choose the second index, which gives a result of 4.
In that case how can one implement it?
diff goes from -u to 0 and then 0 to u
where u = 2500 according to constraints.
That's up to you-- you can use a map, use indices from 0 to 5000, use python with negative indices, overload [] operator, have two different arrays depending on which is bigger, etc.
$$$dp[i][k][sum1] =$$$ maximum possible $$$sum2$$$
Brilliancy