MAXSWT - Editorial

editorial
, , , , , , ,
4

I tried to solve this problem like :- Sort it in the order of {price,sweetness} , and for every index i, finding the upper bound of D - price[i] (the maximum possible pay-able price), lets call that index j.
Now, it reduces down to a range max query on sweetness (because, we’re just finding the maximum possible sweetness you can obtain, given you’ve already picked i) using segment tree in the range i+1 to j. But it gave a AC on one task and TLE on another. I don’t find anything wrong in my approach or in my solution here.

Could someone point out where I went wrong? Thanks.

Edit: Just fixed it. I added extra conditions where n==1 or when D is large enough to be able to buy any two candies. (solution)

So, using a range max query is another valid solution, but maybe an overkill. The editorial solution is clean.

3 Likes
6

Can you guys make a review on my solution . I tried coding up the solution using upper bound but my solution did not pass ,plz tell me where my code goes wrong.

https://www.codechef.com/viewsolution/49068835

7

I guess the constraints was not there given

8

Yeah this also does exactly what our intended solution does. Ultimately we need to find out the second choice for candy out of all available options, which we can easily do by range max query after finding the range.
And yeah this is kinda overkill for the problem, but this idea is simple to implement as segment tree template can be used to quickly code.

1 Like
9

I had also implemented sort of same idea constructed prefix array for sweetness after sorting vector of ({price,sweetness}) and binary search for ith candies which seems fine but don’t know where does it go wrong. Here is my solution O(nlogn) giving wrong answer plz help on that @vichitr and @thunderhashira .

1 Like
10

This is wrong because you are just considering the candy at index j after upper bound on price. But there maybe many candies whose price <= D-P where P is price of first candy. So you need to take maximum sweetness candy among them.
You ignore the fact that there are many possible options for second candy.

11

Looks fine by looking first hand, just see if you are finding lower_bound correctly.

12

Fails for this test-case:

1
5 5
1 4 5 1 3
2 1 2 2 1

Correct output is 4 your code prints 3

1 Like
13

Thanks @cubefreak777 just fixed it got Accepted one thing is missing in my code. I have updated lo=min(lo,i-1) . Here is my Accepted solution using ~prefix array~ and ~binary search

1 Like
14

Your code has same bug as that of mine your logic is perfectly fine. You just take j=min(j,i-1) why ? There is simple explanation to this as you have store the maximum sweetness of candies for range in sweewtness ~~prefix array if your j ~index surpasses the ith~ index it may happen that you consider the ith candies twice which is wrong according to problem. here is your debug~ code

15

I tried sorting the pairs in descending order of sweetness/price and then choosing most suitable 2 elements. I used an approach similar to fractional knapsack.

It clears the given test cases but is showing WA after submission. This is my solution, please tell me where am I wrong.

#include<bits/stdc++.h>
using namespace std;

struct Item{
int price, swt;
};

int custom_sort(struct Item a, struct Item b){

double c1 = (double)a.swt/a.price;
double c2 = (double)b.swt/b.price;

if(c1 == c2){
    return a.swt > b.swt;
}

return c1>c2;

}

int fractional_knap(int Price, struct Item arr[], int n){

    sort(arr, arr+n, custom_sort);


    int currPrice = 0;
    double maxSwt = 0.0;

    int k = 2;

    for(int i=0;i<n;i++){
        if((currPrice + arr[i].price <= Price) && k>0){
            currPrice += arr[i].price;
            maxSwt += arr[i].swt;
            k--;

        }
    }
    return maxSwt;

}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;

while(t--){
    int n, maxPrice;
    cin>>n>>maxPrice;
    
    Item arr[n];
    for(int i=0;i<n;i++){
        cin>>arr[i].price;
    }
    for(int i=0;i<n;i++){
        cin>>arr[i].swt;
    }

    int maxSweet = fractional_knap(maxPrice,arr,n);
    cout<<maxSweet<<'\n';
}

return 0;
}

16

My solution using sparse table for maximum with time complexity of O(nlog(n)(sorting)+(nlog(n)(For sparse) +n(For actually calculating))
Solution

1 Like
17

Fails for this test case

 1
 5 10
 2 3 4 5 6
 2 3 3 4 1

Correct output should be 7 your code print 5.

18

Can someone review my solution? I tried to use binary search to get the max position of the sweetness and then used a sparse table for max. But I am getting TLE on the 2nd task

Code

19

thanks @helpme_152 to debug my code but it fails for this test case: :hot_face:
1
5 10
10 4 5 4 6
12 25 18 20 11

20

if~ condition ~in~ for ~loop ~you ~are ~doing
if(v[i].second>d) continue;
it ~should~ be
if(v[i].first>d) continue;

sometime try to debug it by your own.
I guess this time it should be correct code

1 Like
21

thx @helpme_152 bro🤩

1 Like
22

please check where i am going wrong

my code–>

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define fastio ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define pb push_back
#define ff first
#define ss second
#define endl ‘\n’

bool cmp(pair<int,int> a,pair<int, int> b)
{
if(a.ss==b.ss)
return a.ff<b.ff;
return a.ss>b.ss;
}

ll solve()
{
vector<pair<int,int>> v;
ll n,d,val;
cin>>n>>d;
int i=0;
for(i=0;i<n;i++)
cin>>v[i].ff;
for(i=0;i<n;i++)
cin>>v[i].ss;
sort(v.begin(),v.end(),cmp);
ll max_sweet=0,price=0,cnt=0;
i=0;
while(i<n&&cnt<2)
{
if(price+v[i].ff<=d)
{
cnt++;
max_sweet+=v[i].ss;
price+=v[i].ff;
}
i++;
}
return max_sweet;
}

int main()
{
fastio;
ll tc = 1;
cin >> tc;
for (ll t = 1; t <= tc; t++)
{
// cout << “Case #” << t << ": ";
cout<<solve()<<endl;
//solve();
}
}

23

very good editorial.
Good implementation of set .
I know how to solve this question but not able to implement it.
Thanks for such a editorial.

24

please lemme know why this approach is incorrect