STFOOD - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Hasan
Tester: Teja Vardhan Reddy
Editorialist: Taranpreet Singh

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

There are N types of street food, and for each type of street food, we know the number of stores offering this type of food, the number of people interested in buying this type of food, and the profit per unit for this type of food.

We want to find the maximum profit we can get, by opening a store to offer the food of exactly one of above N types.

We can assume that If there are p people and s stores (including chef’s) for some food type, then Chef will get \lfloor \frac{p}{s} \rfloor people at his store.

QUICK EXPLANATION

  • Each type of store is independent, we can calculate the maximum profit for each store and print maximum.
  • For a food type with P_i people interested, S_i existing stores V_i profit per unit, the number of people at Chef’s store would be \lfloor \frac{P_i}{S_i+1} \rfloor and Chef’s profit would be V_i*\lfloor \frac{P_i}{S_i+1} \rfloor

EXPLANATION

The first thing to notice is that the profit from one type of food is independent of profit from other types of food.

Above allows us to compute profit by opening each type of store and calculating the maximum profit among them. So now we focus on calculating profit from opening a store of one type.

For a food type, P people are interested to buy, S stores already exist for the same type of food and Chef earns V per unit of food. So, after Chef opens a store of this food type, the number of stores become S+1 and the number of people buying from Chef’s store would be \lfloor \frac{P}{S+1} \rfloor Hence, the Chef’s profit becomes V*\lfloor \frac{P}{S+1} \rfloor

We can take the maximum over all the food types and print maximum.

Bonus Problem
In the same problem, Chef opens not one, but K stores, find the maximum profit Chef can get by opening K stores optimally, assuming he can only open at most one store of each type.

Harder version, he can now open multiple stores of the same type, calculate the maximum profit.

TIME COMPLEXITY

The time complexity is O(N) per test case.

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;
			}
			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;
int s,p,v;


int main(){
	//freopen("00.txt","r",stdin);
	//freopen("00o.txt","w",stdout);
	T=readIntLn(1,100);
	while(T--){
		n=readIntLn(1,100);
		int bst = 0;
		for(int i=0;i<n;i++){
			s=readIntSp(1,10000);
			p=readIntSp(1,10000);
			v=readIntLn(1,10000);
			bst = max(bst, (p / (s+1)) * v);
		}
		cout<<bst<<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 s[1234],p[1234],v[1234];
int main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		int i;
		int maxi=0;
		rep(i,n){
			cin>>s[i]>>p[i]>>v[i];
			maxi=max(p[i]/(s[i]+1)*v[i],maxi);
		}
		cout<<maxi<<endl;
	}
	return 0;   
}
Editorialist's Solution
import java.util.*;
import java.io.*;
import java.text.*;
class STFOOD{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    int n = ni();
	    long ans = 0;
	    for(int i = 0; i< n; i++){
	        long s = nl(), p = nl(), v = nl();
	        ans = Math.max(ans, v*(p/(s+1)));
	    }
	    pn(ans);
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	DecimalFormat df = new DecimalFormat("0.00000000000");
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new STFOOD().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

Anyone with solution to these parts?

https://www.codechef.com/viewsolution/29161960
I did exactly the same, why am I getting a WA?

3 Likes

You should do cin >> s >> p >> v
Read the order of input
:slight_smile:


Hey, I got WA by doing the same.
Can you review what was wrong.

Opening K stores – i think the ootimal approach is to greedily take those foods where p and v are high. Take the highest such K untaken food.

You should do cin >> s >> p >> v
Read the order of input
:slight_smile:

why is this code giving WA?

#include <bits/stdc++.h>
using namespace std;
int main()
{
int n; cin>>n;
vector op;
while(n–)
{
int num; cin>>num;
while(num–)
{
float s,p,v;
cin>>s>>p>>v;
op.push_back(v*(floor(p/(s+1))));
}
cout<<*max_element(op.begin(), op.end())<<endl;
op.clear();
}
return 0;
}

The problem was good. But I found the explanation a bit confusing. The order for the three variabels s,v and p was mentioned to be different at different places. Iin the constraints, something else was written instead of what was written in the problem statement.
The same error has also been done by @vaibhav120, I hope the problem setters would keep this in mind from the next time. Even after having the correct logic, having a WA just because of the input and the output comes out to be a bit annoying.

I am getting a WA here, can someone help me out here?
My solution

You are not outputting your answer in new line
Just add that and you will get AC
:slight_smile:

Nope, still no luck. :frowning:
Solution with newline character

As you have done in your earlier submission , you should do P/(S+1) not P/S

:slight_smile:

1 Like

Finally worked, thanks mate! :slight_smile:

1 Like

Can anyone help me with what is wrong in this solution: https://www.codechef.com/viewsolution/29264351

I checked the order of inputs for S, P, V is correct

I used the same approach solving the problem but why I am getting a WA

include “\n” in cout statement …you get right answer.
cout << high<<"\n"; since for every test case you need to show answer in seperate line.

// Problem : Chef and Street Food
// Contest : CodeChef - DSA Learning Series - Week 2
// URL : https://www.codechef.com/LRNDSA02/problems/STFOOD
// Memory Limit : 256 MB
// Time Limit : 1000 ms

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=1;i<=(int)n;i++)
#define REP(i,n) for(int i=0;i<(int)n;i++)
#define ll long long
#define mod 1000000007

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin>>t;
    while(t--){
    	int n;
    	cin>>n;
    	int ans=0;
    	while(n--){
    		int d=0;
    		int s,v,p;
    		cin>>s>>v>>p;
    		d=v*(p/(s+1));
    		ans=max(ans,d);
    	}
    	cout<<ans<<endl;
    }
    return 0;
}

> my code is correct.But why showing WA?

There is something wrong here
Check the order of input
:slight_smile:

#include<bits/stdc++.h>
using namespace std;
#define loop for (int i = 0; i < N; i++)
int main()
{
int T, N;
int S, P, V;
cin >> T;
long int chefMaxProfit = 0;
while(T- -) {
cin >> N;
loop // i=0; to N;
{
cin >>S>>P>>V;
//long int totalProfit = P * V;
int totalShops = S + 1;
long int profit = (P/totalShops) * V;
if(chefMaxProfit < profit) chefMaxProfit = profit;
}
cout<< chefMaxProfit << endl;
}
return 0;
}

My code is returning WA can someone tell me why?Preformatted text