I'm struggling with a problem can someone please help me ?

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

Автор Bryma, история, 5 лет назад, По-английски

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

Bryma
5 лет назад
41

Комментарии (25)

Показать архивные | Написать комментарий?

0rez

5 лет назад, скрыть # |

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

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

-8

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

→ Ответить

0rez

5 лет назад, скрыть # ^ |

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

→ Ответить

newbie_forever_at_cp

5 лет назад, скрыть # ^ |

← Rev. 3 →

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)

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

-11

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

→ Ответить

newbie_forever_at_cp

5 лет назад, скрыть # ^ |

← Rev. 2 →

`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";`
`}`

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

-8

incorrect too.. :(

→ Ответить

newbie_forever_at_cp

5 лет назад, скрыть # ^ |

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

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

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

→ Ответить

0rez

5 лет назад, скрыть # ^ |

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

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

You said that so if k — yi = fullness so why we search for dp[a][100][0..100] ? if we need 100 of fulness ?

→ Ответить

0rez

5 лет назад, скрыть # ^ |

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.

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

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

→ Ответить

0rez

5 лет назад, скрыть # ^ |

yeah

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

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

→ Ответить

0rez

5 лет назад, скрыть # ^ |

← Rev. 3 →

#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.

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

That solution is incorrect :(

→ Ответить

0rez

5 лет назад, скрыть # ^ |

← Rev. 2 →

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

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

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.

→ Ответить

0rez

5 лет назад, скрыть # ^ |

Can you try to run it 1 last time?

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

any other ideas ?

→ Ответить

0rez

5 лет назад, скрыть # ^ |

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. :'-(

→ Ответить

HydrO7gen

5 лет назад, скрыть # |

+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.

→ Ответить

Bryma

5 лет назад, скрыть # ^ |

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

→ Ответить

MarioPariona117

5 лет назад, скрыть # ^ |

← 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;
}

→ Ответить