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.
