### it_is_not_an_alt's blog

By it_is_not_an_alt, history, 4 weeks ago,

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?

• +5

 » 4 weeks ago, # |   +9 Can you prove this problem is not from an ongoing contest?
•  » » 4 weeks ago, # ^ |   0 It's not probably. I think i have seen a similar problem.
•  » » » 4 weeks ago, # ^ |   0 Can you provide a link?
•  » » 4 weeks ago, # ^ |   0 I cant prove that. But I am willing to wait for x days, where x is the maximum number of days(reasonable) you think a contest can run for.
•  » » » 4 weeks ago, # ^ |   0 Where did you find this problem?
•  » » » » 4 weeks ago, # ^ |   0 past contest
•  » » » » » 4 weeks ago, # ^ |   -15 What contest?
•  » » » » » » 4 weeks ago, # ^ |   0 Local Contest of School
 » 4 weeks ago, # |   0 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])