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

I'm struggling with a problem can someone please help me ?
Автор Bryma, история, 4 года назад, По-английски

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.

  • Проголосовать: нравится
  • -8
  • Проголосовать: не нравится

»
4 года назад, # |
← 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<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).

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
        ← 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)

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится -11 Проголосовать: не нравится

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

          → Ответить
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
            ← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится 
            `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";`
`}`
            → Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +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].

      → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 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 ?

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +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.

          → Ответить
      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

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

        → Ответить
        • »
          »
          »
          »
          »
          4 года назад, # ^ |
            Проголосовать: нравится +8 Проголосовать: не нравится

          yeah

          → Ответить
          • »
            »
            »
            »
            »
            »
            4 года назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

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

            → Ответить
            • »
              »
              »
              »
              »
              »
              »
              4 года назад, # ^ |
              ← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится 
              #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.

              → Ответить
              • »
                »
                »
                »
                »
                »
                »
                »
                4 года назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                That solution is incorrect :(

                → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                  ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

                  → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 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.

                  → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  Can you try to run it 1 last time?

                  → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 0 Проголосовать: не нравится

                  any other ideas ?

                  → Ответить
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  4 года назад, # ^ |
                    Проголосовать: нравится 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. :'-(

                  → Ответить
»
4 года назад, # |
  Проголосовать: нравится +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.

→ Ответить
  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +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

    → Ответить
    • »
      »
      »
      4 года назад, # ^ |
      ← 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<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;
}
      → Ответить