Bryma's blog

By Bryma, history, 5 weeks ago, In English

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
  • Answer : 2
  • 2
  • 100 20
  • 100 100

Answer : 1

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

 
 
 
 
  • Vote: I like it
  • -8
  • Vote: I do not like it

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Bryma (previous revision, new revision, compare).

»
5 weeks ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

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<y_i$$$, $$$dp[i][j][k]=dp[i-1][j][k]$$$. Here $$$dp[i][j][k]$$$ is 0 if $$$j<0$$$. Complexity is O(100*100*NUM_DISHES).

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    It's a little bit too complicated for me to understand.. can you please send me some code ?

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    And the answer is ( a is the number of dishes) dp[a][a][a] ?

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      It is $$$max(d[a][100][0], dp[a][100][1], \dots, dp[a][100][100])$$$.

      • »
        »
        »
        »
        5 weeks ago, # ^ |
        Rev. 3   Vote: I like it +8 Vote: I do not like it

        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, # ^ |
            Vote: I like it -11 Vote: I do not like it

          Can you please provide a c++ code ? ( not need to be exactly but i can understand a code better ) .

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            Rev. 2   Vote: I like it +8 Vote: I do not like it
            `Try this...` 
            ``
            `#include<bits/stdc++.h>`
            `#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<int, int>`
            `#define keyy pair<pair<int, int>, int>`
            `#define keyyy pair<pair<int, int>, pair<int, int>>`
            `#define keyd pair<double, double>`
            `#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<<i<<" "<<hap<<" "<<cnt<<"\n";`
            `        int full = i;`
            `        f(j, 1, n+1)`
            `        {`
            `            if(not ok[j] && (full + a[j].ff) <= 100)`
            `            {`
            `                full += a[j].ff; hap += a[j].ss;`
            `                cnt++;`
            `            }`
            `        }`
            ``        
            `        if(hap >= 100)`
            `            ans = max(ans, cnt);`
            ``        
            `    }`
            ``    
            `    // f(i, 1, n+1) { f(j, 1, 101) cout<<dp[i][j]<<" "; cout<<"\n"; } cout<<"\n";`
            `    // f(i, 1, n+1) { f(j, 1, 101) cout<<idx[i][j]<<" "; cout<<"\n"; } cout<<"\n";`
            ``    
            `    cout<<ans<<"\n";`
            `}`
            
            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              incorrect too.. :(

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Can you send the input for which this is incorrect ? Im too bored to find the case.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it -8 Vote: I do not like it

                  It doesn't shows ..

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    could you please send me a c++ code to understand it faster ? :)

  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i can't understand why we have dp[i][j-xi][k-yi] if xi is the hapiness

    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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, # ^ |
            Vote: I like it +8 Vote: I do not like it

          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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        And we need to iterate like this ? for(int i = 0;i<a;i++) { for(int j = 0;j<100;j++) { for(int k = 0;k<100;k++) { dp[i][j][k] ?

        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          yeah

          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            could you please send a c++ code i can't implement it solo.

            • »
              »
              »
              »
              »
              »
              »
              5 weeks ago, # ^ |
              Rev. 3   Vote: I like it 0 Vote: I do not like it
              #include<bits/stdc++.h>
              using namespace std;
              typedef long long ll;
              #define mod 1000000007
              int dp[101][101][101];
              pair<int,int> 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<n;++i)
                      cin>>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<<ans;
              }
              

              I assumed number of dishes<=100. Not sure if the code works though.

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                Thanks the number of dishes is <= 50

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                That solution is incorrect :(

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                  Rev. 2   Vote: I like it 0 Vote: I do not like it

                  I messed up in the base case :/. Try now. I edited the code.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  still incorrect

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Can you try to run it 1 last time?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  now it's a TLE

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  any other ideas ?

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  5 weeks ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  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, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Don't you want to practice this problem for future contests ? :)

              • »
                »
                »
                »
                »
                »
                »
                »
                5 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                the first number in input — Xi = fullness and the second — Yi = happiness

»
5 weeks ago, # |
  Vote: I like it +12 Vote: I do not like it

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, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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   Vote: I like it +12 Vote: I do not like it

      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<bits/stdc++.h> 
      #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<int> l(n + 1), f(n + 1);
         for(int i = 0; i < n; i++){
            cin >> l[i] >> f[i];
         }  
         vector<vector<int>> dp(101, vector<int> (5001, -1000));
         dp[0][0] = 0
         int ans = 0;
         for(int i = 1; i <= n; i++){
            vector<vector<int>> 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, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Thank you so much !!!

      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Could you please explain what are you doing here ?