blablablacksheep's blog

By blablablacksheep, history, 3 months ago,

We have 2 arrays $A$ and $B$ of length $n$ each. We are required to pick $k$ elements from both the arrays say $A_{i_{1}}, A_{i_{2}}, ... A_{i_{k}}$ and $B_{i_{1}}, B_{i_{2}}, ... B_{i_{k}}$ such that the sum $A_{i_{1}} + A_{i_{2}} + ... + A_{i_{k}} > \lfloor{\frac{S_{A}}{2}}\rfloor$ and $B_{i_{1}} + B_{i_{2}} + ... + B_{i_{k}} > \lfloor{\frac{S_{B}}{2}}\rfloor$. Here $S_{A}$ and $S_{B}$ denote the sum of the arrays A and B respectively.$\newline$ We also want to print the indices we have chosen, if such a choice is possible.$\newline$ Also, pay attention to the fact that we are picking elements from $B$ with the same indices ${i_{1}, i_{2}, ... , i_{k}}$ that we have used for $A$.$\newline$ Constraints :- $A_{i}, B_{i} \le 10^{9}$ and, size of the arrays $\le 10^{5}$. Please can anyone help me in solving this??

• +12

 » 3 months ago, # |   0 use priority queue or just sort the array to pick the K largest element from the array
•  » » 3 months ago, # ^ |   0 That simply won't work as we need to pick the elements at the same set of indices from $B$ which we have chosen from $A$
•  » » » 3 months ago, # ^ |   0 ohh , I missed that
 » 3 months ago, # |   0 Can you send the link to this problem?
•  » » 3 months ago, # ^ |   0 Sorry, I don't have the link, an interviewer asked me in a coding interview.
 » 2 months ago, # |   0 Not sure if this solution works, but here it is:Let Sa = sum of all elements of A, divided by two.Similarly, Sb = sum of all elements of B divided by two.In beginning, choose the max K numbers from array A. If their sum is smaller than Sa, the answer obviously does not exist. Otherwise, run a While loop, in condition: while the sum of chosen elements of B is smaller than the desired sum (that is, Sb), find an initially chosen index i, such that it has the least value of Ai. ( Note that once we change this i, we cant change it anymore). Then set that index to the position of the highest value of B that we haven't chosen that position yet, update the answer and check again if the current sum of chosen elements is ≥ Sb. Keep doing this until the answer is not found. If at some point inside the While, sum of chosen elements of A becomes less than Sa, then the answer doesn't exist.
 » 2 months ago, # | ← Rev. 6 →   0 try something like the trick from time is money:let $f(i) = lambda * a[i] + (1 - lambda) * b[i]$if we take the indices that score the biggest $k$ values of $f$, this will obviously maximize sum of $A$s for $lambda = 1$ and maximize sum of $B$s for $lambda = 0$. The more $lambda$ increases the more we care about $B$s. If we binary search $lambda$ such that the algo cares enough about $A$s to get a sum of $A$s big enough, the resulting sum of $B$s should be the theoretical maximum.