I am trying to solve round #383 problem D (div 2):
Problem statement:here
I can complete every step up till the usage of DP. In my code, I used 2-D DP like what was mentioned in the editorial. Somehow, my code is failing the following test case:
10 5 100
6 18 35 6 87 58 4 53 37 71
465782 57034 547741 748298 315223 370368 679320 349012 9740 622511
1 2
10 9
6 7
3 6
7 1
Expected Output: 2050129
My Program Output: 1836591
My attempt:
#include <iostream>
#include <vector>
#include <unordered_map>
//#define debug
using namespace std;
#define ll long long
#define v64 vector<ll>
#define um unordered_map<ll,ll>
#define mp make_pair
ll n,m,w,a,b;
typedef struct woman {
ll w, b;
} woman;
woman ww[1005];
ll par[1005], rk[1005],dp[1005][1005];
um cw, cb;
int val[1005];
ll find(ll x) {
ll p = x;
if(par[x]!=x) p = find(par[x]);
return par[x] = p;
}
inline void un(ll x,ll y) {
ll px = find(x), py = find(y);
if(px != py) {
if(rk[px] > rk[py]) {
par[py] = px;
rk[px] += rk[py];
} else {
par[px] = py;
rk[py] += rk[px];
}
}
}
ll solve(ll cur, ll t) {
if(dp[cur][t]!=-1) return dp[cur][t];
if(cur <= n && t>0) {
if(ww[cur].w<=t) {
if(val[find(cur)]) {
val[find(cur)] = 0;
ll a1 = 0;
if(cw[find(cur)]<=t) a1 = cb[find(cur)]+solve(cur+1,t-cw[find(cur)]);
ll a2 = ww[cur].b+solve(cur+1,t-ww[cur].w);
val[find(cur)] = 1;
ll a3 = solve(cur+1,t);
return dp[cur][t] = max(a1,max(a2,a3));
} else {
return dp[cur][t] = solve(cur+1,t);
}
} else {
return dp[cur][t] = solve(cur+1,t);
}
}
return dp[cur][t]=0;
}
int main(void) {
#ifdef debug
freopen("in","r",stdin);
#else
ios_base::sync_with_stdio(false);
cin.tie(0);
#endif
cin >> n >> m >> w;
fill_n(rk,n+1,1);
fill_n(val,n+1,1);
for(int i = 1; i <= n; ++i) fill_n(dp[i],w+1,-1);
for(int i = 1; i <= n; ++i) {
cin >> ww[i].w;
par[i] = i;
}
for(int i = 1; i <= n; ++i) {
cin >> ww[i].b;
}
for(int i = 1; i <= m; ++i) {
cin >> a >> b;
un(a,b);
}
for(int i = 1 ; i <= n; ++i) {
cw[find(i)] += ww[i].w;
cb[find(i)] += ww[i].b;
}
cout << solve(1,w) << endl;
return 0;
}
If I remove the DP (from the solve function), my program will pass the test case. Hence, it is clear that my DP is wrong. However, I do not know how to write the DP properly. Could someone please advise me on why my code is wrong?
Your problem is that dp[i][j] is not uniquely defined. If you can use the current element (i.e. val[find(cur)] is not 0), the value that your dp[cur][t] will be assigned is different that the value if val[find(cur)] is 0. As the value of dp[cur][t] is only calculated once, whenever you want to use it again, it might have an incorrect value (for the other value of val[find(cur)]). To solve your problem, you might want to expand 1 dimension your dp, with a third parameter only 0 or 1, stating the value of val[find(cur)] when you calculated this. Another way to solve your problem is to iterate through groups of friendship, instead of through individuals. I think this latter approach is the one suggested by the editorial
If I iterate through groups, that means I will be considering groups as a whole right? But the problem states that we can choose none, one or all from one particular group. So how do I consider individuals if I iterate through groups?
Create an arrays of vectors groups[]. You will insert individual i in group[find(i)]. Then, dp[i][j] will represent the maximum beauty you can get with j kg to go and being in the i-th group. In each group, and for each weight, you should check if it is better to choose the whole group or just an individual of the group (since you have in the vector group[i] the members that belong to this group, this will be easy.) Check my submission 22835923 for details (my dp is bottom-top by the way, a paradigm you should consider for bigger dp's).
Thanks a lot! I really appreciate your help. May I ask why do you say that bottom-up dp is recommended for bigger dp's? Is it easier to code than top-down dp?
No, actually it might be a more difficult to code. It depends on the problem. The greatest disadvantage for top-down dp (and in general with any recursion method, such as dfs), is that the implicit memory used for the recursion might be completely used, and if this happens, you will get an unexplainable TLE or MLE or runtime error. I've had a lot of errors of this kind and they are really frustrating!
I have studied your code carefully. There is one statement I don't understand:
This line searches for the maximum beauty that can be obtained when we are at the last group for a certain weight limit right?
If we use a larger weight limit, won't we intuitively get a better beauty value? So why can't we simply use the following instead:
where wi is the maximum weight limit given by the input.
Well, my code is a little lazy. dp[i][j] stores the maximum beauty that can be achieved using the first i groups and exactly j weight. Then, it is not necessary that the maximum weight will contain the maximum beauty. Take for example 3 hoses that are all friends, all weighting 1 and beauty 1, and the maximum weight the scenario can stand is 2. The maximum beauty attainable will be 1, when the weight supported by the scenario is just 1, instead of the maximum 2