# SLUSH - EDITORIAL

Practice

Contest: Division 1

Contest: Division 2

Tester: Teja Vardhan Reddy

Editorialist: Teja Vardhan Reddy

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.

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 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){
}
long long readIntLn(long long l,long long 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);
while(T--){

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){
} else {
}
sm_c += C[i];
}
assert(sm_c >= n);
long long sol = 0;
for(int i=1;i<=n;i++){
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

// 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.

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

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 Ill do some more debugging and if no result then Iâ€™ll ask for help here

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

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.

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?

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