MAXSWT - Editorial

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Daanish Mahajan
Tester: Manan Grover
Editorialist: Vichitr Gandas

DIFFICULTY:

EASY

PREREQUISITES:

Greedy, Set or Map or Priority Queue

PROBLEM:

Given N different types of candies with price and sweetness. Now given Chef has D dollars and can take a maximum of 2 candies one in each hand, find the maximum total sweetness he can collect under the given constraints if each type of candy can be taken at most once.

EXPLANATION

Idea is to try every candy and pick best choice available for another candy and take maximum of sweetness.
Bruteforce idea is to loop over all (i,j) pairs and see if they can be picked together i.e. if their price sum <=D. But this takes O(N^2) time. We can optimise it to O(NlogN). Lets see how!

First of all, lets make a vector of \{price, sweetness\} pairs and sort it in ascending order of price. We are sorting so that we can process in order of price. For example if current price is P then just need to pick maximum sweetness candy out of those candies who price is less than or equal to D-P.

We can maintain a multiset S of candies which can be picked as alternatives and we can keep them sorted according to sweetness hence we can pick the most sweet candy easily as last item in multiset.

We can process from most priced candy to least priced. Initially S would be empty. Maintain a pointer i which denotes upto which index we have inserted in the set. Now if we are currently at index j then we know that if we move to j-1, all the candies which were suitable option for j would also be suitable for j-1 as P_{j-1} \le P_j.
For current index j we can keep inserting i^{th} candy until we satisfy i < j and P_i + P_j \le D. Keep incrementing i by 1 until both conditions are satisfied.
Also if we had inserted upto index i and we come upto index j \le i traversing from back, we need to remove current i.e. j^{th} candy from S as we can not pick j^{th} candy twice.

If we select j^{th} candy then best choice among available options would be the last one in set S hence take the sum of sweetness of these 2 candies. If S is empty then just consider taking j^{th} candy alone. Final answer is maximum of this value among all j.

TIME COMPLEXITY:

O(NlogN) per test case

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
#define pb push_back 
#define ll long long int
#define pii pair<int, int>

using namespace std;

const int maxt = 2.5e5;
const int maxn = 1e5;
const int maxtn = 1e6;
const int maxd = 1e9;
const int maxp = 1e9;
const int maxs = 1e9;

struct Cmp
{
    bool operator()(const pii& v1, const pii& v2) const
    { 
        return v1.second == v2.second ? v1.first < v2.first : v2.second < v1.second; 
    }
};

int main()
{ 
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t, n, d; cin >> t;
    int tn = 0;
    while(t--){
        cin >> n >> d; tn += n;
        vector<pii> v(n);
        for(int i = 0; i < n; i++)cin >> v[i].first;
        for(int i = 0; i < n; i++)cin >> v[i].second;
        sort(v.begin(), v.end());
        multiset<pii, Cmp> mset;
        int ans = 0;
        int ptr = 0;
        for(int i = n - 1; i >= 0; i--){
            while(ptr < i && v[ptr].first + v[i].first <= d){
                mset.insert(v[ptr]);
                ++ptr;
            }
            multiset<pii>::iterator it = mset.find(v[i]);
            if(i <= ptr - 1 && it != mset.end())mset.erase(it);
            if(v[i].first <= d){
                ans = max(ans, v[i].second + (mset.empty() ? 0 : (*mset.begin()).second));
            }
        }
        cout << ans << endl;
    }
    assert(tn <= maxtn);
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int t;
  cin>>t;
  while(t--){
    int n, d;
    cin>>n>>d;
    int p[n], s[n];
    for(int i = 0; i < n; i++){
      cin>>p[i];
    }
    for(int i = 0; i < n; i++){
      cin>>s[i];
    }
    multimap<int, pair<int, int>> m;
    m.insert({0, {0, 0}});
    for(int i = 0; i < n; i++){
      m.insert({p[i], {s[i], s[i]}});
    }
    int x = 0, y = 0;
    for(auto it = m.begin(); it != m.end(); it++){
      int z = (*it).second.second;
      if(z > x){
        y = x;
        x = z;
      }else if(z > y){
        y = z;
      }
      (*it).second = {x, y};
    }
    int ans = 0;
    for(int i = 0; i < n; i++){
      if(d < p[i]){
        continue;
      }
      int temp = s[i];
      auto it = m.upper_bound(d - p[i]);
      it--;
      if(d - p[i] < p[i]){
        temp += (*it).second.first;
      }else{
        if((*it).second.first == s[i]){
          temp += (*it).second.second;
        }else{
          temp += (*it).second.first;
        }
      }
      ans = max(ans, temp);
    }
    cout<<ans<<"\n";
  }
  return 0;
}
Editorialist's Solution
/*
 * @author: vichitr
 * @date: 25th July 2021
 */

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fast ios::sync_with_stdio(0); cin.tie(0);

void solve() {
	int n, d; cin >> n >> d;
	int p[n], s[n];
	for (int i = 0; i < n; i++)
		cin >> p[i];
	for (int i = 0; i < n; i++)
		cin >> s[i];
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		if (p[i] <= d)
			v.push_back({p[i], s[i]});
	}
	sort(v.begin(), v.end());

	int ans = 0;
	int i = 0;
	multiset<pair<int, int>> st;
	for (int j = v.size() - 1; j >= 0; j--) {
		while (i < j and v[j].first + v[i].first <= d) {
			st.insert({v[i].second, v[i].first});
			i++;
		}
		auto it = st.find({v[j].second, v[j].first});
		if (j <= i - 1 and it != st.end()) st.erase(it);
		int here = v[j].second;
		if (!st.empty())
			here += (*st.rbegin()).first;
		ans = max(ans, here);
	}
	cout << ans << '\n';
}

signed main() {
	fast;

#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif

	int t = 1;
	cin >> t;
	for (int tt = 1; tt <= t; tt++) {
		// cout << "Case #" << tt << ": ";
		solve();
	}
	return 0;
}

VIDEO EDITORIAL:

If you have other approaches or solutions, let’s discuss in comments.If you have other approaches or solutions, let’s discuss in comments.

1 Like

I attempted the same using DP. But I kept getting “Runtime Error(Other)”.
Link to approach: https://www.codechef.com/viewsolution/49047593

Possible problems in my approach:

  • Memory usage

Is there anyway I could improve this? or is Greedy is the optimal/only solution?

1 Like

DP won’t work as value of D is upto 10^9. I don’t think there is any DP of size O(n) possible here.

7 Likes

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

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

I guess the constraints was not there given

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

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

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.

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

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

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

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

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

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

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.

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

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

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

thx @helpme_152 bro🤩

1 Like