Bryma's blog

I'm struggling with a problem can someone please help me ?
By Bryma, history, 4 years 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

Comments Comments (25)
| Write comment?
»
4 years 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).

→ Reply
  • »
    »
    4 years 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] ?

    → Reply
    • »
      »
      »
      4 years 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])$$$.

      → Reply
      • »
        »
        »
        »
        4 years 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)

        → Reply
        • »
          »
          »
          »
          »
          4 years 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 ) .

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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";`
`}`
            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              incorrect too.. :(

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years 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.

                → Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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].

      → Reply
      • »
        »
        »
        »
        4 years 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 ?

        → Reply
        • »
          »
          »
          »
          »
          4 years 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.

          → Reply
      • »
        »
        »
        »
        4 years 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] ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +8 Vote: I do not like it

          yeah

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years 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.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years 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.

              → Reply
              • »
                »
                »
                »
                »
                »
                »
                »
                4 years ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                That solution is incorrect :(

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  Can you try to run it 1 last time?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years ago, # ^ |
                    Vote: I like it 0 Vote: I do not like it

                  any other ideas ?

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 years 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. :'-(

                  → Reply
»
4 years 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.

→ Reply
  • »
    »
    4 years 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

    → Reply
    • »
      »
      »
      4 years 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;
}
      → Reply