Electr0's blog

How to solve this problem?
By Electr0, history, 3 years ago, In English

Suppose we have 2 arrays of size n (say A and B) and we have to select k indices i1,i2,i3....ik, such that all are valid indices (i.e all belong to [0,n-1) ) .And let valA = $$$\sum_{j=1}^{k} A_{ij}$$$ and let valB = $$$\sum_{j=1}^{k} B_{ij}$$$. Then min(valA,valB) should be maximum. How to solve this? I tried using dp but couldnt figure out how to move from dp[i-1] to dp[i].
Is there any other way to think about it?

  • Vote: I like it
  • +5
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Can you prove this problem is not from an ongoing contest?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If the sum of elements are small, then dp[i][x] denote the max value of sum of B[i] you can get if you take i element with sum x from A, Then do a knapsack like dp,

dp[i][x]=max(dp[i-1][x-A[i]]+B[i],dp[i-1][x])

→ Reply