EATTWICE - EDITORIAL

PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Setter: Hasan Jaddouh

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

DIFFICULTY:

PREREQUISITES:

Greedy.

PROBLEM:

A restaurant makes N dishes in M days with $i$th dish on day d_i and has tastiness v_i. Chef can eat atmost two dishes and not both on the same day. Find the maximum total tastiness of the dishes he can eat.

EXPLANATION

Let us group dishes based on the day they are made.

On each day,since chef can eat atmost one dish, he will only prefer to eat the dish with highest tastiness. So let us calculate the highest taste of a dish on each day (lets represent it by t_i for i th day).

Now, he will eat on the two days which have highest and second highest value of t_i among all days when a dish is made in the restaurant.

TIME COMPLEXITY

O(n+m). First part of grouping takes O(n) time. Second part of finding max and second max element in array t among all the m days takes O(m) time.

Bonus: We can also reduce time complexity to O(n) which I leave it for the comments.

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#include <set>
#include <assert.h>
using namespace std;
 
 
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
            
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            assert(cnt>0);
            if(is_neg){
                x= -x;
            }
            assert(l<=x && x<=r);
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
int T;
int n,m;
int sm_n=0;
int sm_m=0;
 
int mx[100100];
 
int main(){
    //freopen("01.txt","r",stdin);
    //freopen("01o.txt","w",stdout);
    T=readIntLn(1,1000);
    while(T--){
        n=readIntSp(2,100000);
        m=readIntLn(2,100000);
        sm_n += n;
        sm_m += m;
        assert(n<=1000000);
        assert(m<=1000000);
        for(int i=1;i<=m;i++){
            mx[i]=0;
        }
        set<int> g;
        for(int i=1;i<=n;i++){
            int d,v;
            d=readIntSp(1,m);
            g.insert(d);
            v=readIntLn(1,1000000000);
            mx[d]=max(mx[d],v);
        }
        assert(g.size()>1);
        sort(mx+1,mx+1+m);
        cout<<mx[m]+mx[m-1]<<endl;
    }
    assert(getchar()==-1);
} 
Tester's Solution
//teja349
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16); cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 << endl; prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
 
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define flush fflush(stdout) 
#define primeDEN 727999983
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
// find_by_order()  // order_of_key
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
int d[123456],v[123456],maxi[123456];
int main(){
    std::ios::sync_with_stdio(false); cin.tie(NULL);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        int i;
        rep(i,n){
            cin>>d[i]>>v[i];
            maxi[d[i]]=max(maxi[d[i]],v[i]);
        }
        vi vec;
        rep(i,n){
            if(maxi[d[i]]==0)
                continue;
            vec.pb(maxi[d[i]]);
            maxi[d[i]]=0;
        }
        assert(vec.size()>=2);
        sort(all(vec));
        int siz=vec.size();
        cout<<vec[siz-1]+vec[siz-2]<<endl;
    }
    return 0;   
}

Feel free to Share your approach, If it differs. Suggestions are always welcomed. :slight_smile:

How is the time complexity O(n+m) ? Isn’t the tester solution’s time complexity will be greater than that

A better and simple to understand code is this. after filling in the array, just sort it in descending order. Time complexity isn’t that good, but not bad either

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
void func()
{
ll n,m,i,d,x;
cin>>n>>m;
ll a[m]={0};
for(i=0;i<n;i++)
{
cin>>d>>x;
if(a[d-1]<x)
a[d-1]=x;
}
std::sort(a,a+m,greater());
cout<<a[0]+a[1]<<endl;
}
int main()
{
ll T;
cin>>T;
while(T–)
func();
return 0;
}

2 Likes

My approach was using a vector of pairs using greedy.

ll t,n,m;
cin>>t;
while(t–){
cin>>n>>m;
vector<pair<ll,ll>> vp;
for(ll i=0;i<n;i++){
ll a,b;
cin>>a>>b;
vp.push_back(make_pair(b,a));
}
sort(vp.begin(),vp.end(),sortinrev);
ll taste=vp[0].first,i=1;
while(vp[0].second==vp[i].second)i++;
taste+=vp[i].first;
cout<<taste<<"\n";
}

This will not get AC because you are not considering of the case in which max and second max tastiness or both max tastiness have same day then you have to look for 3rd max.

I thought solution was to find maximum and second maximum with a constraint that day should be different .
My code

#include<bits/stdc++.h>
using namespace std;
struct token
{
int d,t;
};
int main()
{
int t;
cin>>t;
while(t–)
{
int n,m;
cin>>n>>m;
int max1=INT_MIN,max2=INT_MIN;
token x[n];
for(int i=0;i<n;i++)
{
cin>>x[i].d>>x[i].t;
}
int z=0;
for(int i=0;i<n;i++)
{
if(max1<x[i].t)
{
max1=x[i].t;
z=x[i].d;
}
}
x[z].t=INT_MIN;
for(int i=0;i<n;i++)
{
if(max2<x[i].t && z!=x[i].d)
{
max2=x[i].t;
}
}
cout<<max1+max2<<endl;
}
}

I got AC for this .
I stored the descending sorted tastes with there day number .
Stored the maximum taste as sum
Now iterated while we have same days ahead
So after the iteration you will get maximum taste but with a different date .
So… :slight_smile:

1 Like

I was wondering whats wrong with this logic: create an unordered map of pairs and for each di, only store the highest vi. This way the unordered map would only have the highest tastiness for each date. Loop through for max tastiness, store in first max. Delete this key. Find max again store in second max. Yes I know this is not efficient but like I thoght at least it would give the right answer…

Thanks I got you Nice approach .

1 Like

This is the O(n) approach:

Maintain a D1 (Day1) and D2 (Day2) as days of largest and second largest tastiness days (they should have different days, obviously, i.e. D1 != D2) respectively, and their corresponding tastiness as T1 and T2.

  1. Run a loop for the dishes.
  2. If the dish has tastiness greater than equal to T1, also if the day of the dish served is not equal to D1, then make T2=T1 and D2=D1, and the corresponding dish day and tastiness is to be assigned to D1 and T1. Else, assign D1 and T1 to corresponding dish day and tastiness.
  3. Else if, dish tastiness is greater than T2 and corresponding dish day is not D1, then the corresponding dish day and tastiness is to be assigned to D2 and T2.
  4. Finally, output the value T1 + T2.

Here is my code:
(R1SYB0 - Online C++0x Compiler & Debugging Tool - Ideone.com)

What a solution bro…:heart_eyes:

Here is my approach:

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

#define mod 1000000007
#define fastIO ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
#define point(n) fixed<<setprecision(n)
typedef long long ll;
typedef unsigned long ul;
typedef unsigned long long ull;

int main()
{
    fastIO
    int t;
    cin>>t;
    while(t--){
    	ll n,m;
    	cin>>n>>m;
    	vector<ll> v(n),d(n);
    	map<ll, ll> mp;
    	for(int i=0;i<n;i++){
    		cin>>d[i]>>v[i];
    		if(mp[d[i]] < v[i])
    			mp[d[i]]=v[i];
    	}
    	vector<ll> res;
    	for(auto& i:mp){
    		res.push_back(i.second);
    	}
    	sort(res.begin(),res.end(),greater<int>());
    	cout<<res[0]+res[1]<<'\n';
    }
    return 0;
}

I am extremely overwhelmed that you liked my solution. I am not sure that whether you meant sarcasm or not but just to clarify you, I got AC for that. I will explain my code for you, as I see you are at 1 star.
The case of 2nd max,3rd max doesn’t arise, because I have used Di as the index and for the same day, I have taken account of the largest value. I hope this is clear and study code a little further before commenting. Thank you :smile: Hope you have a great day ahead.

1 Like

Not at all bro I just loved your solution I am just looking at others solution and people are using pair vector and so many things Your code is sweet and simple .

1 Like

Exactly. My main intention of posting the code was for newbies. Glad you liked it. Happy Coding

My algorithm is similar to setters algorithm, but it has produced TLE as output.I cant understand What mistake I did .Can an one help me?

This is my program.Thanks!

t=int(input())
for _ in range(t):
n,m=map(int,input().split())
days=[ ]
taste=[ ]
for i in range(n):
d,t=map(int,input().split())
if d not in days:
days.append(d)
taste.append(t)
else:
taste[days.index(d)]=max(taste[days.index(d)],t)
taste.sort()
print(taste[-1]+taste[-2])

I was getting a runtime error in below code. I have used the priority queue with comparator and pair to store day and tastiness. Please help me to fix it out
#include
#include
using namespace std;
struct compare
{
bool operator()(pair<int,int>p1,pair<int,int>p2)
{return (p1.second<p2.second);
}
};
int main() {
// your code goes here
int t,n,m,d,v,i;
int count=0;
int k;
cin>>t;
priority_queue<pair<int,int>,vector<pair<int,int>>,compare>pq;
while(t–)
{
cin>>n>>m;
for(i=0;i<n;i++)
{
cin>>d>>v;
pq.push(make_pair(d,v));

    }
    
  pair<int,int>p = pq.top();
  pq.pop();
   k = p.first;
   count =  p.second;
     while(!pq.empty())
    {
        p= pq.top();
        pq.pop();
        if(p.first!=k)
        {
            count = count + p.second;
            break;
        }
    }
    cout<<count<<endl;
}

return 0;

}

https://www.codechef.com/viewsolution/24920208
Can you get the error?
Logic is same but still getting wa , don’t know why?

You forgot to add the case where v=v1 :smiley:
replace :
if(v>v1&&d!=d1)
to
if(v>=v1&&d!=d1)

Happy Coding :smile:

This code works. Check the bugs - mainly you gave output inside the dish query loop, which should have been outside the for loop.
(3JexJd - Online C Compiler & Debugging Tool - Ideone.com)