Блог пользователя WorstCoder45

Google OA Question — Hard DP optimization.
Автор WorstCoder45, история, 8 месяцев назад, По-английски

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.

Теги dp
  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
8 месяцев назад, # |
← Rev. 4   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      8 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 месяцев назад, # ^ |
          Проголосовать: нравится 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]?

        → Ответить
        • »
          »
          »
          »
          »
          8 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          → Ответить
          • »
            »
            »
            »
            »
            »
            8 месяцев назад, # ^ |
              Проголосовать: нравится 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!

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              8 месяцев назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                8 месяцев назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                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.

                → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  8 месяцев назад, # ^ |
                    Проголосовать: нравится +13 Проголосовать: не нравится

                  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.

                  → Ответить
  • »
    »
    8 месяцев назад, # ^ |
    ← Rev. 6   Проголосовать: нравится +3 Проголосовать: не нравится 
    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)
    → Ответить
»
8 месяцев назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

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

→ Ответить
  • »
    »
    8 месяцев назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Brilliancy

    → Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You are god!

    → Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    can you elaborate a little?

    → Ответить
  • »
    »
    3 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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;
}
    → Ответить