Google OA Question — Hard DP optimization.

→ Обратите внимание

До соревнования
Educational Codeforces Round 173 (Rated for Div. 2)
32:12:20
Зарегистрироваться »

→ Трансляции

aryanc403

До начала 34:22:19

Всё →

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	3985
2	jiangly	3814
3	jqdai0815	3682
4	Benq	3529
5	orzdevinwang	3526
6	ksun48	3517
7	Radewoosh	3410
8	hos.lyric	3399
9	ecnerwala	3392
9	Um_nik	3392

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	169
2	maomao90	162
2	Um_nik	162
4	atcoder_official	161
5	djm03178	158
6	-is-this-fft-	157
7	adamant	155
8	awoo	154
8	Dominater069	154
10	luogu_official	151

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

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

Google OA Question — Hard DP optimization.

Автор WorstCoder45, история, 9 месяцев назад, По-английски

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.

WorstCoder45
9 месяцев назад
19

Комментарии (19)

Написать комментарий?

donot

9 месяцев назад, # |

← Rev. 4 →

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.

→ Ответить

Red0

9 месяцев назад, # ^ |

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

→ Ответить

Sahilamin219

9 месяцев назад, # ^ |

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

→ Ответить

donot

9 месяцев назад, # ^ |

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.

→ Ответить

WorstCoder45

9 месяцев назад, # ^ |

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

→ Ответить

donot

9 месяцев назад, # ^ |

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.

→ Ответить

WorstCoder45

9 месяцев назад, # ^ |

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!

→ Ответить

donot

9 месяцев назад, # ^ |

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.

→ Ответить

WorstCoder45

9 месяцев назад, # ^ |

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.

→ Ответить

donot

9 месяцев назад, # ^ |

+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.

→ Ответить

Snapper_001

9 месяцев назад, # ^ |

← Rev. 6 →

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)

→ Ответить

Brovko

9 месяцев назад, # |

+14

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

→ Ответить

WorstCoder45

9 месяцев назад, # ^ |

Brilliancy

→ Ответить

its_time_to_grow

4 месяца назад, # ^ |

You are god!

→ Ответить

SSKMF

4 месяца назад, # ^ |

You should be more careful with your words.

→ Ответить

Yagnik007

4 месяца назад, # ^ |

can you elaborate a little?

→ Ответить

alpha_6124

4 месяца назад, # ^ |

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;
}

→ Ответить

Newtonian278

4 месяца назад, # ^ |

which platform you are verifying your sol ?

→ Ответить

alpha_6124

4 месяца назад, # ^ |

Just testcase

→ Ответить

Соревнования по программированию 2.0

Время на сервере: 23.12.2024 09:22:41 (k3).

Десктопная версия, переключиться на мобильную.

При поддержке