### Bryma's blog

By Bryma, history, 5 weeks ago,

In celebration of the 4th of July, Aldo goes to an American buffet. In this buffet, there are different types of dishes. The -th plate fills a percentage of your stomach and gives you a percentage of happiness.

Aldo can eat a plate at the most once, because he wants variety, and he wants to achieve 100% happiness without going over 100% full. Help Aldo determine the maximum number of dishes he can eat while satisfying his restrictions.

Notes:

It is valid to exceed 100% happiness, but not 100% fullness. It is guaranteed that Aldo can always reach 100% happiness.

Input : The first line contains an integer, the number of dishes. The following lines contain 2 integers each, and the percentages of fullness and happiness that they cause, respectively.

Example input :

• 3
• 60 50
• 30 50
• 50 60
• 2
• 100 20
• 100 100

Please, i need at least a hint. I tried to solve it solo but i can't.

• -8

 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).
 » 5 weeks ago, # |   0 Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).
 » 5 weeks ago, # | ← Rev. 2 →   +17 Maintain a 3-D dp. $dp[i][j][k]$ denotes that given dishes 1 to i, what is the maximum number of dishes that can be eaten so that happiness $\ge j$ and fullness=k. Base case is $dp[0][j][k]=0$. So, if the happiness and fullness of $i^{th}$ dish are $x_i$ and $y_i$, then $dp[i][j][k]=max(dp[i-1][j-x_i][k-y_i]+1,dp[i-1][j][k])$ for $k \ge y_i$. For $k •  » » 5 weeks ago, # ^ | -8 It's a little bit too complicated for me to understand.. can you please send me some code ? •  » » 5 weeks ago, # ^ | -8 And the answer is ( a is the number of dishes) dp[a][a][a] ? •  » » » 5 weeks ago, # ^ | +8 It is$max(d[a][100][0], dp[a][100][1], \dots, dp[a][100][100])$. •  » » » » 5 weeks ago, # ^ | ← Rev. 3 → +8 I am actually not sure whether this approach works. Here is my simple solution, Since we dont need to have exactly 100% fullness, maintain a 1d table of size 100. dp[i] holds maximum happiness I can get if I have i% stomach full. Also maintain index array which holds the index of the element used to obtain this happiness. Then for all i, remove the index used to obtain ith element and then sort the remaining elements in ascending order based on the % fullness. Take the maximum number you can and then check if the cumulative happiness >= 100. If yes, take the max of this for all i from 1 to 100. Therotically this wont go more than O(100 * N) •  » » » » » 5 weeks ago, # ^ | -11 Can you please provide a c++ code ? ( not need to be exactly but i can understand a code better ) . •  » » » » » » 5 weeks ago, # ^ | ← Rev. 2 → +8 Try this...  #include #define pb push_back //#define mp make_pair #define fastread ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); #define openfile ifstream cin; ofstream cout; cin.open("input.txt"); cout.open("output.txt"); #define f(i, x, y) for(int i = x; i < y; i++) #define all(X) X.begin(), X.end() #define int long long #define ll long long #define key pair #define keyy pair, int> #define keyyy pair, pair> #define keyd pair #define ff first #define ss second #define double long double const int mod = 1e9 + 7; // const int mod = 998244353; const int inf = 1e18; using namespace std;  main() {  fastread;  int n; cin>>n; key a[n+1]; f(i, 1, n+1) cin>>a[i].ff>>a[i].ss;  int dp[n+1][105]; memset(dp, 0, sizeof(dp));  int idx[n+1][105]; memset(idx, -1, sizeof(idx));  sort(a+1, a+n+1);   f(i, 1, n+1)  {  f(j, 1, 101)  {  dp[i][j] = dp[i-1][j]; idx[i][j] = idx[i-1][j];  if(a[i].ff <= j && dp[i][j] < dp[i-1][j-a[i].ff] + a[i].ss)  {  dp[i][j] = dp[i-1][j-a[i].ff] + a[i].ss;  idx[i][j] = i;  }  }  }   int ans = -1;  f(i, 1, 101)  {  // if(i != 30) continue;  bool ok[n+1]; memset(ok, 0, sizeof(ok));  int id = n, j = i, hap = 0, cnt = 0;;  while(id > 0 && idx[id][j] > 0)  {  if(id == idx[id][j])  {  hap += dp[id][j];  j -= a[id].ff;  cnt++; ok[id] = true;  }  id--;  }  // cout<= 100)  ans = max(ans, cnt);   }   // f(i, 1, n+1) { f(j, 1, 101) cout< •  » » » » » » » 5 weeks ago, # ^ | -8 incorrect too.. :( •  » » » » » » » » 5 weeks ago, # ^ | 0 Can you send the input for which this is incorrect ? Im too bored to find the case. •  » » » » » » » » » 5 weeks ago, # ^ | -8 It doesn't shows .. •  » » 5 weeks ago, # ^ | 0 could you please send me a c++ code to understand it faster ? :) •  » » 5 weeks ago, # ^ | 0 i can't understand why we have dp[i][j-xi][k-yi] if xi is the hapiness •  » » » 5 weeks ago, # ^ | +8 If you have dishes 1 to i and you want to achieve happiness$\ge$j with fullness equal to k, there are 2 cases: 1.You eat dish i. Now you have dishes 1 to i-1 and you want happiness$\ge j-x_i$with fullness$k-y_i$. This is$dp[i-1][j-x_i][k-y_i]\$. 2. You do not eat dish i. Then same happiness and fullness are needed with dishes 1 to i-1. That is dp[i-1][j][k].
•  » » » » 5 weeks ago, # ^ |   0 You said that so if k — yi = fullness so why we search for dp[a][100][0..100] ? if we need 100 of fulness ?
•  » » » » » 5 weeks ago, # ^ |   +8 You want happiness to be >=100 while fullness maybe any number from 0 to 100. So, the optimal answer will be the maximum taken over all possible fullness.
•  » » » » 5 weeks ago, # ^ |   0 And we need to iterate like this ? for(int i = 0;i
•  » » » » » 5 weeks ago, # ^ |   +8 yeah
•  » » » » » » 5 weeks ago, # ^ |   0 could you please send a c++ code i can't implement it solo.
•  » » » » » » » 5 weeks ago, # ^ | ← Rev. 3 →   0 #include using namespace std; typedef long long ll; #define mod 1000000007 int dp[101][101][101]; pair dish[101]; int solve(int i, int j,int k) { if(i<0) return 0; if(j<0) { return (k>=dish[i].second) ? max(solve(i-1,j,k-dish[i].second)+1,solve(i-1,j,k)) : solve(i-1,j,k); } if(dp[i][j][k]!=-1) return dp[i][j][k]; return dp[i][j][k]= (k>=dish[i].second)? max(solve(i-1,j-dish[i].first,k-dish[i].second)+1,solve(i-1,j,k)) : solve(i-1,j,k); } int main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int n; cin>>n; for(int i=0;i<=100;++i) for(int j=0;j<=100;++j) for(int k=0;k<=100;++k) dp[i][j][k]=-1; for(int i=0;i>dish[i].second>>dish[i].first; int ans=0; for(int i=0;i<=100;++i) ans=max(ans,solve(n-1,100,i)); cout<
•  » » » » » » » » 5 weeks ago, # ^ |   0 Thanks the number of dishes is <= 50
•  » » » » » » » » 5 weeks ago, # ^ |   0 That solution is incorrect :(
•  » » » » » » » » » 5 weeks ago, # ^ | ← Rev. 2 →   0 I messed up in the base case :/. Try now. I edited the code.
•  » » » » » » » » » 5 weeks ago, # ^ |   0 still incorrect
•  » » » » » » » » » 5 weeks ago, # ^ |   0 maybe some corner cases ?i come with a solution to generate every possible susbet but it wiil work only for n <= 20 , the constrains are n <= 50 tho.
•  » » » » » » » » » 5 weeks ago, # ^ |   0 Can you try to run it 1 last time?
•  » » » » » » » » » 5 weeks ago, # ^ |   0 now it's a TLE
•  » » » » » » » » » 5 weeks ago, # ^ |   0 any other ideas ?
•  » » » » » » » » » 5 weeks ago, # ^ |   0 The idea is still the same, but we'll need to establish the dp in the base case of j<0 also(since I'm using recursion there, it's not really the base case and is the reason for TLE.) We'll need to precompute the values to be returned there. But as I said earlier, it was my last attempt. :'-(
•  » » » » » » » » » 5 weeks ago, # ^ |   0 Don't you want to practice this problem for future contests ? :)
•  » » » » » » » » 5 weeks ago, # ^ |   0 the first number in input — Xi = fullness and the second — Yi = happiness
 » 5 weeks ago, # |   +12 Hello Bryma,please do not seek help with ONLY problem statements.Provide a link to the problem, so people can make sure it is not from a live contest, before they help you. Thanks.
•  » » 5 weeks ago, # ^ |   +3 Ok but it's a spanish problem so you need to translate it — https://omegaup.com/arena/replica-cpio-2020/practice/#problems/4-de-julio
•  » » » 5 weeks ago, # ^ | ← Rev. 2 →   +12 I got accepted.It is only dp[x][y][z] // x : cur_plate, y : fullness, z = happiness.Firstly, I did simply that and got MLE.My AC code below. #include #define cpu() ios::sync_with_stdio(false); cin.tie(nullptr) #define ps() cout << "\n" #define pb push_back #define ff first #define ss second typedef long long ll; using namespace std; const int MOD = 1e9 + 7, MOD1 = (119 << 23) | 1; const int INF = 1e9 + 5, MAX = 2e5 + 5; int main(){ cpu(); int n; cin >> n; vector l(n + 1), f(n + 1); for(int i = 0; i < n; i++){ cin >> l[i] >> f[i]; } vector> dp(101, vector (5001, -1000)); dp[0][0] = 0 int ans = 0; for(int i = 1; i <= n; i++){ vector> cur = dp; for(int j = 0; j <= 100; j++){ for(int k = 0; k <= 5000; k++){ if(j >= l[i - 1] && k >= f[i - 1]) dp[j][k] = max(dp[j][k], cur[j - l[i - 1]][k - f[i - 1]] + 1); if(k >= 100){ ans = max(ans, dp[j][k]); } } } } cout << ans << "\n"; return 0; } `
•  » » » » 5 weeks ago, # ^ |   0 Thank you so much !!!
•  » » » » 5 weeks ago, # ^ |   0 Could you please explain what are you doing here ?