WorstCoder45's blog

Google OA Question — Hard DP optimization.
By WorstCoder45, history, 8 months ago, In English

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.

Tags dp
  • Vote: I like it
  • +3
  • Vote: I do not like it

»
8 months ago, # |
← Rev. 4   Vote: I like it +1 Vote: I do not like it

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:

$$$\text{dp[n'][k'][diff] = max(dp[n'-1][k'-1][diff] , b[i] + dp[n'-1][k'-1][diff + a[i] - b[i]])}$$$

The first term is if you don't choose index n', the second is if you choose it.

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Pls teach how to notice such recursive methods. I've learned to picture as a tree, but that never works for me.

    → Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why are you adding min(a[i], b[i]) in diff ?

    → Reply
    • »
      »
      »
      8 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        8 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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]?

        → Reply
        • »
          »
          »
          »
          »
          8 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
          • »
            »
            »
            »
            »
            »
            8 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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!

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              8 months ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                8 months ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 months ago, # ^ |
                    Vote: I like it +13 Vote: I do not like it

                  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.

                  → Reply
  • »
    »
    8 months ago, # ^ |
    ← Rev. 6   Vote: I like it +3 Vote: I do not like it 
    Assuming diff = sum1-sum2

dp[n'][k'][diff] = max value in both of them such that by 
                   adding this to sum1 , they can be equal
Ex:  diff = 3 , dp[n'][k'][diff] =5
     means sum1 = 5 + 3 , sum2 = 5     , 5 is max possible we can make here

Ex:  diff = -3 , dp[n'][k'][diff] = 5
     means sum1 = 5 - 3 , sum2 = 5     , 5 is max possible we can make here

Transiition: (you see in above example that the value that dp store is sum2 right)
               Thats why we do b[i]
     dp[n'][k'][diff] = max(dp[n'-1][k'-1][diff] , b[i] + dp[n'-1][k'-1][diff + a[i] &mdash; b[i]])

     Now in the end, what values we get in diff , if diff > 0 , ans = max(ans , dp[n][k][diff])
                                                  else   ans = max(ans , dp[n][k][diff] - diff)
    → Reply
»
8 months ago, # |
  Vote: I like it +14 Vote: I do not like it

$$$dp[i][k][sum1] =$$$ maximum possible $$$sum2$$$

→ Reply
  • »
    »
    8 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Brilliancy

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

    You are god!

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

      You should be more careful with your words.

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

    can you elaborate a little?

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

    getting wrong answer please anyone correct 

    Your code here...

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using ll= long long;
typedef vector<int> vi;
typedef vector<long long> vll;
int dp[51][51][2503];
int fun(vi &arr1,vi &arr2,int ind,int ct,int sum){
    if(ind==arr1.size()){
        if(ct==0)return 0;
        return -1e6;
    }
    int ans=0;
    if(dp[ind][ct][sum]!=-1)return dp[ind][ct][sum];
    if(ct>0)ans=max(ans,fun(arr1,arr2,ind+1,ct-1,sum+arr2[ind])+arr1[ind]);
    ans=max(ans,fun(arr1,arr2,ind+1,ct,sum));

    return  dp[ind][ct][sum]=ans;
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

    int n=5;
   vi arr1={6,3,6,5,1};
   vi arr2={1,4,5,9,2};
   int k=3;
   memset(dp,-1,sizeof(dp));
   int ans=0;
   int x=fun(arr1,arr2,0,k,0);
// //    cout<<x<<endl;
        for(int sum=0;sum<=2500;sum++){
            ans=max(ans,min(sum,dp[n][0][sum]));
        }
        // for(int i=0;i<n;i++){
        //     for(int j=0;j<=k;j++){
        //         for(int sum=0;sum<=2500;sum++){
        //             ans=max(ans,min(sum,dp[i][j][sum]));
        //         }
        //     }
        // }
   cout<<ans<<endl;
    return 0;
}
    → Reply