SLUSH - 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:

There are M flavours of drinks each of C_i cups. They are N people entering the store in that order. Each person has a favourite drink. If his favourite flavour is available in the store, he pays F_i and buys one cups of it otherwise pays B_i and accepts any flavour of one cup (chef can choose this flavour). Now we want to maximise the profit.

QUICK EXPLANATION

  • We assign a person’s favourite flavour if its present. Otherwise we assign to him later one of flavours left behind after assigning favourite flavours for others.

EXPLANATION

Claim: If a person’s(lets say p_1) favourite flavour is not present, its always optimal to give that person a flavour (lets say x) such that no other person misses that flavour later with it as their favourite flavour.

Proof:
Lets says p_2 was the first person who missed flavour x with flavour x as his favourite flavour. Now let the total profit was G. Now lets say p_2 was given flavour y since x was not available. Now, if we had given p_1 flavour y then x would have been available for p_2 with rest being same so we would have given x to p_2. In such a scenario, total profit is G + F[p_2]-B[p_2]) (\gt G). Hence, proved.

Now, the above one proves that we want to maximise people getting their favourite flavours. So if a person’s favourite flavour is not present, lets not assign him a flavour immediately. We will assign him one of the flavours left over at the end. Then, nobody would have missed favourite flavour because of him.

TIME COMPLEXITY

O(n+m).

SOLUTIONS:

Setter's Solution
#include <iostream>
#include <algorithm>
#include <string>
#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;
            }
            if(!(l<=x && x<=r)){
                cerr<<l<<" "<<r<<" "<<x<<endl;
            }
            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 C[100100];
int D[100100];
int B[100100];
int F[100100];
int ans[100100];
int sm_n=0;
int sm_m=0;
int main(){
    //freopen("03.txt","r",stdin);
    //freopen("03o.txt","w",stdout);
    T=readIntLn(1,1000);
    while(T--){
        
        n=readIntSp(2,100000);
        m=readIntLn(2,100000);
        sm_n += n;
        sm_m += m;
 
        assert(sm_n <= 1000000);
        assert(sm_m <= 1000000);
        long long sm_c=0;
        for(int i=1;i<=m;i++){
            if(i==m){
                C[i]=readIntLn(1,n);
            } else {
                C[i]=readIntSp(1,n);
            }
            sm_c += C[i];
        }
        assert(sm_c >= n);
        long long sol = 0;
        for(int i=1;i<=n;i++){
            D[i]=readIntSp(1,m);
            F[i]=readIntSp(2,1000000000);
            B[i]=readIntLn(1,F[i]-1);
            if(C[D[i]] > 0){
                sol += F[i];
                ans[i] = D[i];
                C[D[i]]--;
            } else {
                sol += B[i];
                ans[i] = -1;
            }
        }
        int cur = 1;
        for(int i=1;i<=n;i++){
            if(ans[i]!=-1)continue;
            while(C[cur] == 0)cur++;
            ans[i] = cur;
            C[cur] --;
        }
        cout<<sol<<endl;
        for(int i=1;i<=n;i++){
            if(i==n){
                cout<<ans[i]<<endl;
            } else{
                cout<<ans[i]<<" ";
            }
        }
    }
    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 c[123456],d[123456],b[123456],f[123456],happy[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,m){
            cin>>c[i];
        }
        rep(i,n){
            cin>>d[i]>>f[i]>>b[i];
            d[i]--;
        }
        ll ans=0;
        rep(i,n){
            happy[i]=0;
            if(c[d[i]]){
                c[d[i]]--;
                happy[i]=1;
                ans+=f[i];
            }
            else
                ans+=b[i];
        }
        int j=0;
        cout<<ans<<endl;
        rep(i,n){
            if(happy[i]){
                cout<<d[i]+1<<" ";
                continue;
            }
            while(c[j]==0)
                j++;
            cout<<j+1<<" ";
            c[j]--;
 
        }
        cout<<endl;
    }
    return 0;   
}

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

9 Likes

Used a similar logic as that of editorial , still getting WA .
Can someone pls check the code?

https://www.codechef.com/viewsolution/24931432
thanks in advance!

1 Like

Why I am getting Seg fault

#include<bits/stdc++.h>
using namespace std;
unsigned long long int t,n,i,j,l,m,a,b,d,c[100004],ans[100004],k[100004];
unsigned long long int sum;
int main()
{

scanf("%llu",&t);
while(t--)
{
sum=0;
    scanf("%llu %llu",&n,&m);
    for(i=1;i<=m;i++)
    scanf("%d ",c+i);
    memset(k,0,sizeof(k));
    j=0;
    for(i=1;i<=n;i++)
    {
        
        scanf("%llu %llu %llu",&d,&a,&b);
        if(c[d]>0)
        {
        sum+=a;
        c[d]--;
        ans[i]=d;
        }
        else
        {
            sum+=b;
            k[j]=i;
        j++;
        }
        
    }
    l=0;
    for(i=1;i<=m;i++)
    {
        while(c[i]>0)
        {
            ans[k[l]]=i;
            l++;
            if(l==j)
            goto aa;
            c[i]--;
        }
    }
    aa:;
    printf("%llu\n",sum);
    for(i=1;i<=n;i++)
    printf("%llu ",ans[i]);
    printf("\n");
}
return 0;

}

same i also applied same logic first i precalculated which indexes are gonna left with positive remaining then i give one by one them…still wa

2 Likes

Same here :frowning: Ill do some more debugging and if no result then I’ll ask for help here :slight_smile:

I don’t really know. What is this?
Edit: I understand now it is label. :slight_smile:
Also please send link to submission, that way we can point out line numbers as well. :slight_smile:

Well, I tried the same approach as in editorial. i tried to store the indices in an array which cannot get their favourite flavour. Then i gave them the remaining one’s which are left.

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

You can see my approach here,but it’s getting wrong answer.
P.s-It passes the given test case.

If someone can point out what’s going wrong.Thank You!

1 Like

The array ans is of size n.
while printing the ans array the for loop runs from 1 to n , instead it should be n-1.

hope this helps!

No bro, it’s correct i indexed the arrays from 1 to n.
And even the sample case given in problem shows correct output in my compiler.
:confused:

I need help regarding language.
I wrote a solution to the problem SLUSH (https://www.codechef.com/COOK107B/problems/SLUSH/)
in Java -
(https://www.codechef.com/viewsolution/24920106)
which gave TLE.
Then I wrote the same logic in Cpp and got an AC - (https://www.codechef.com/viewsolution/24924305)
I used Fast I/O in both. Could anyone explain why?

5 Likes

@tarang4: problem is at line 37-41. You are modifying the map on which you are iterating which causes the iterator to point to somewhere else instead of intended memory locations. Sometimes you may get other verdict like TLE or RE due to this mistake.
You could have done same thing by:

set<ll> to_remove;
for(it1=mp1.begin(); it1!=mp1.end(); it1++) {
    if(mp1[it1->first] == 0)
        to_remove.insert(it1->first);
}
for(set<ll>::iterator itt2 = to_remove.begin(); itt2 != to_remove.end(); itt2++) { 
	mp1.erase(*itt2);
}

Also in line 42-52 you are reducing count to 0 and then pick next element. You could have done whole thing like this by removing the code (lines 37-41) and replacing if in line 47 with while.

Other method (if you want to do same thing):
remove lines 37-41 and replace lines 25-35 by :

if(mp1.find(x)!=mp1.end())
        {
        	mp1[x]--;
        	if(mp1[x]==0)
        		mp1.erase(x);
			sum += y;
        	check.push_back(x);
		}
		else
		{
			sum += z;
			check.push_back(-1);
		}

Here is my solution: https://www.codechef.com/viewsolution/24933315
Hope it helps!

3 Likes

I wrote a solution in Java of complexity O(T(N+M))*
I was using old Reader class for fast io (Solution 1), but after the contest got over I tried with GFG Reader class and same logic got accepted (Solution 2 Fast IO). I want to know why the time bound for Java is so tight?
Could anyone please explain why?

We can do this problem by a first finding all the customers who can get their favourite drinks and updating profit along with that.

sum=sum+F[i];

Now the trick >> the ones who didn’t get their favourite drink can get any drinks left with shoopkeeper so update sum accordingly.

sum = sum + B[i];

2 Likes

Here is my implementation in c++ which got AC.

#include

using namespace std;

int main()
{
int t;
cin>>t;
while(t–)
{
long long int n,m;
cin>>n>>m;
long long int c[m],i,d[n],f[n],b[n],a[n],sum=0,k;

	for(i=0;i<m;i++)
		cin>>c[i];
	
	for(i=0;i<n;i++)
	{
		cin>>d[i]>>f[i]>>b[i];
		if(c[d[i]-1]>0)
		{
			c[d[i]-1]--;
			a[i]=d[i];
			sum=sum+f[i];
		}
		else
		{
			a[i]=0;
			sum=sum+b[i];
		}
	}
	for(k=0;k<n;k++)
	{
		if(a[k]==0)
		{
			for(i=0;i<m;i++)
			{
				if(c[i]>0)
				{
					c[i]--;
					a[k]=i+1;
					break;
				}
			}
		}
	}
	cout<<sum<<endl;
	for(i=0;i<n;i++)
	{
		cout<<a[i]<<" ";
	}
	cout<<endl;
}

}

3 Likes

line no 47 it should be while instead of if.

I used a similar logic , I don’t why I am getting wrong answer
https://www.codechef.com/viewsolution/24925567

Wow i never saw that Fi>Bi during the contest
I was thinking both Fi and Bi could be any number less than 1e9
But what do you think will be the solution for this problem if Fi and Bi could be any number less than 1e9 i.e. Fi>Bi or Fi<Bi or Fi=Bi
Thanks in advance.

3 Likes

I tried exactly the same approach in Java I got TLE

Same approach in Java .Result is TLE.I used Fast io
https://www.codechef.com/viewsolution/24933215.Can anyone help me.

Used same approach in Python3, but getting NZEC error. Please help.

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

Edit: Probably it is an IndexError, that is causing NZEC.