CHPINTU - Editorial

PROBLEM LINK:

Practice
Div-2 Contest

Author: Manav Patel
Tester: Suchan Park
Editorialist: William Lin

DIFFICULTY:

Cakewalk

PREREQUISITES:

Ad-hoc

PROBLEM:

There are M types of fruits and N baskets of fruits. Each basket contains one type of fruit and has a certain non-negative price. You want to select a fruit such that there exists at least one basket with that fruit and you should buy all baskets with that fruit. Find the minimum possible cost.

QUICK EXPLANATION:

Iterate over each fruit type and check it.

EXPLANATION:

To be able to choose a fruit i, there must be at least one basket containing fruit i. To check if fruit i can be chosen, we can loop through all baskets to find any basket with fruit i:

bool found=false;
for(int j=0; j<n; ++j) {
	if(f[j]==i) {
		found=true;
	}
}
//if found is true then we can choose fruit i

Let’s calculate the cost of choosing fruit i, which will be the sum of the prices of the baskets with fruit i. We can make a few changes to our previous code:

bool found=false;
int sum=0;
for(int j=0; j<n; ++j) {
	if(f[j]==i) {
		found=true;
		sum+=p[j];
	}
}
//if found is true then we can choose fruit i
//sum is the cost of choosing fruit i

Lastly, we should run the code above for each fruit i so that we can find which fruits can be chosen and the costs of those fruits. Our answer is the minimum cost out of all fruits which can be chosen.

int ans=1e9; //some arbitrarily large value
for(int i=1; i<=m; ++i) {
	//try fruit i
	bool found=false;
	int sum=0;
	for(int j=0; j<n; ++j) {
		if(f[j]==i) {
			found=true;
			sum+=p[j];
		}
	}
	//if found is true then we can choose fruit i
	//sum is the cost of choosing fruit i
	if(found) {
		//update the answer with the cost for fruit i
		ans=min(sum, ans);
	}
}
//ans is now the answer

HIDDEN TRAPS:

  • It is insufficient to check if the sum of costs of the baskets for a fruit is positive to determine if a type of fruit has at least one basket. This is because the prices of baskets can be 0.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
void solve()
{
    int N, M;
    cin >> N >> M;  // M - Fruits, N - Baskets
    int F[N], P[N];
    for(int i = 0; i < N; i++)
    {
        cin >> F[i];
    }
    for(int i = 0; i < N; i++)
    {
        cin >> P[i];
    }
    int final_price = 1000000;
    for(int i = 1; i <= M; i++)
    {
        int price = 0;
        bool flag = false;
        for(int j = 0; j < N; j++)
        {
            if(F[j] == i)
            {
                price += P[j];
                flag = true;
            }
        }
        if(flag)
        {
        	if(price < final_price)
        	{
        		final_price = price;
			}
		}	
    }
	cout << final_price << "\n";
}
 
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        solve();
    }
    return 0;
}
Tester's Solution
#include <bits/stdc++.h>
 
const int BUFFER_SIZE = int(1.1e5);
 
char _buf[BUFFER_SIZE + 10];
int _buf_pos, _buf_len;
 
char seekChar() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    assert(_buf_pos < _buf_len);
    return _buf[_buf_pos];
}
 
bool seekEof() {
    if(_buf_pos >= _buf_len) {
        _buf_len = fread(_buf, 1, BUFFER_SIZE, stdin);
        _buf_pos = 0;
    }
    return _buf_pos >= _buf_len;
}
 
char readChar() {
    char ret = seekChar();
    _buf_pos++;
    return ret;
}
 
int readInt(int lb, int rb) {
    char c = readChar();
    int mul = 1;
    if(c == '-') {
        c = readChar();
        mul = -1;
    }
    assert(isdigit(c));
 
    long long ret = c - '0';
    char first_digit = c;
    int len = 0;
    while(!seekEof() && isdigit(seekChar()) && ++len <= 19) {
        ret = ret * 10 + readChar() - '0';
    }
    ret *= mul;
 
    if(len >= 2) assert(first_digit != '0');
    assert(len <= 18);
    assert(lb <= ret && ret <= rb);
    return (int)ret;
}
 
void readEoln() {
    char c = readChar();
    //assert(c == '\n');
    assert(c == '\n' || (c == '\r' && readChar() == '\n'));
}
 
void readSpace() {
    assert(readChar() == ' ');
}
 
void run() {
    int N = readInt(1, 50);
    readSpace();
    int M = readInt(1, 50);
    readEoln();
    std::vector<int> F(N), P(N);
    std::vector<bool> used(M);
    std::vector<int> cost(M);
    for(int i = 0; i < N; i++) {
        F[i] = readInt(1, M) - 1;
        if(i+1 < N) readSpace(); else readEoln();
        used[F[i]] = true;
    }
    for(int i = 0; i < N; i++) {
        P[i] = readInt(0, 50);
        if(i+1 < N) readSpace(); else readEoln(); 
        cost[F[i]] += P[i];
    }
    std::vector<int> cand;
    for(int i = 0; i < M; i++) {
        if(used[i]) cand.push_back(cost[i]);
    }
    printf("%d\n", *std::min_element(cand.begin(), cand.end()));
}
 
int main() {
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif
 
    int T = readInt(1, 1000);
    readEoln();
 
    while(T--) {
        run();
    }
    return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;

int n, m, f[50], p[50];

void solve() {
	//input
	cin >> n >> m;
	for(int i=0; i<n; ++i)
		cin >> f[i];
	for(int i=0; i<n; ++i)
		cin >> p[i];

	int ans=1e9; //some arbitrarily large value
	for(int i=1; i<=m; ++i) {
		//try fruit i
		bool found=false;
		int sum=0;
		for(int j=0; j<n; ++j) {
			if(f[j]==i) {
				found=true;
				sum+=p[j];
			}
		}
		//if found is true then we can choose fruit i
		//sum is the cost of choosing fruit i
		if(found) {
			//update the answer with the cost for fruit i
			ans=min(sum, ans);
		}
	}
	cout << ans << "\n";
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	while(t--)
		solve();
}

Please give me suggestions if anything is unclear so that I can improve. Thanks :slight_smile:

12 Likes

why it isn’t accepting this giving wrong answer

#include <bits/stdc++.h>

using namespace std;

int main()

{

int t;

cin>>t;

for(int i=1;i<=t;i++)

{

    int n,m;

    cin>>n>>m;

    int f[50],p[50],t[50];

    memset(t,0,sizeof(t));

    for(int j=0;j<n;j++)

    {

        cin>>f[j];

    }

    for(int j=0;j<n;j++)

    {

        cin>>p[j];

    }

    for(int k=0;k<n;k++)

    {

        t[f[k]-1]=t[f[k]-1]+p[k];

    }

    

    sort(t,t+m);

    for(int k=0;k<m;k++)

    {

        if(t[k]!=0){

        cout<<t[k]<<"\n";

        break;  }

                }

}

}

1 Like

“hidden traps”

4 Likes

why is my solution not working? please answer

#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin>>t;
while(t>0){
int n,m;
cin>>n>>m;
vectorf(n+1);
vectorp(n+1);
vectora(m+1,0);
f[0]=0;
p[0]=0;
for(int i=1;i<=n;i++){
cin>>f[i];
}
for(int i=1;i<=n;i++){
cin>>p[i];
}
for(int i=1;i<=n;i++){
a[f[i]]+=p[i];
}
sort(a.begin(),a.end());
for(int i=1;i<=m;i++){
if(a[i]>0)
{
cout<<a[i]<<endl;
break;
}
}
t–;
}
}

1 Like

“hidden traps”

3 Likes

ohhkay I got it Thanks!!

Wow, probably the best editorial ever read!!! Just loved it.

1 Like

thank you

My solution https://www.codechef.com/viewsolution/30494808

why this is wrong ? Pls help

#include
#include
using namespace std;
int main(){
int t,n,m,i,j,sum=0,ans=INT_MAX;
int f[10000],p[10000];
cin>>t;
while(t–){
cin>>n>>m;
for(i=0;i<n;i++){
cin>>f[i];
}
for(j=0;j<n;j++){
cin>>p[j];
}
for(i=1;i<=m;i++)
{
bool found=false;
int sum=0;
for(j=0;j<n;j++)
{
if(f[j]==i){
found=true;
sum+=p[j];
}
}
if(found){
ans = min(ans,sum);
}
}
cout<<ans<<endl;
}
}

what is wrong int this solution
c++:
#include<bits/stdc++.h>
using namespace std;

int main() {

int t;
cin>>t;
vector a(60,0);
vector b(60,0);
vector c(60,0);
int m,n;
int min;
for(int i=0;i<t;i++){

cin>>n>>m;

for(int j=0;j<n;j++){
  c[j]=-1;
  cin>>a[j];
}

for(int j=0;j<n;j++){
cin>>b[j];
}

min=200000;
for(int j=0;j<n;j++){
if(c[a[j]-1]==-1){
c[a[j]-1]=b[j];
}else{
c[a[j]-1]+=b[j];
}
}
for(int j=0;j<m;j++){
if(c[j]>=0 && min>=c[j]){
min=c[j];
}
}
cout<<min<<" "<<endl;

}

return 0;
}

^^^

Thanks a lot!

@everule1 but i have checked even then answer was not accepted

Please use ` `` before and after the code to format it correctly. The code is not comprehensible.

1 Like
#include<climits>
using namespace std;
int main(){
    int t,n,m,i,j,sum=0,ans=INT_MAX;
    int f[10000],p[10000];
    cin>>t;
    while(t--){
        cin>>n>>m;
        for(i=0;i<n;i++){
            cin>>f[i];
        }
        for(j=0;j<n;j++){
            cin>>p[j];
        }
        for(i=1;i<=m;i++)
        {
            bool found=false;
            int sum=0;
            for(j=0;j<n;j++)
            {
                if(f[j]==i){
                    found=true;
                    sum+=p[j];
                }
            }
            if(found){
                ans = min(ans,sum);
            }
        }
        cout<<ans<<endl;
    }
    
}

ans is initialised only once, you need to initialise it for each test case. Generally to avoid stuff like this, you should declare all the variables inside the while loop, since you haven’t used them outside the loop. also iterator variables should be in the loop, not declared seperately. It’s not necessary, but is more readable, and simpler to debug. The scope should be the minimum possible. also use ‘\n’ instead of endl, since it’s not interactive and endl is slow.

1 Like

What’s wrong in my solution…(in c language)

#include <stdio.h>
#include <limits.h>

int main(void) {
// your code goes here
int t;
scanf("%d", &t);
while(t–)
{
int n, m;
scanf("%d %d", &n, &m);
int type[n+1], price[n+1], hash[m+1];
for(int i=1; i<=m; i++)
hash[i]= 0;

    for(int i=1; i<=n; i++)
        scanf("%d ", &type[i]);
    for(int i=1; i<=n; i++)
        scanf("%d ", &price[i]);
   
   for(int i=1; i<= n; i++)
   {
       int temp= type[i];
       hash[temp]+= price[i];
   }
   int min= INT_MAX;
   for(int i=1; i<= m; i++)
   {
       if(hash[i]<min && hash[i]>0)
       min= hash[i];
   }
   printf("%d\n", min);
}
return 0;

}

Can’t find an error in my code. Please Help!!
#include <bits/stdc++.h>
using namespace std;
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define int long long
#define rep(i,a,b) for(int i=a;i<b;i++)
int32_t main()
{
IOS;
int t;
cin>>t;
while(t–)
{
int n, m;
cin>>n>>m;
int a[n][2];
int sum[m]={0};
int count[m]={0};
rep(i,0,n) cin>>a[i][0];
rep(i,0,n) cin>>a[i][1];
rep(i,0,n) sum[a[i][0]-1]+=a[i][1];
rep(i,0,n) count[a[i][0]-1]++;
vector<pair<int,int>> vect;
rep(i,0,n) vect.push_back(make_pair(sum[i],count[i]));
sort(vect.begin(),vect.end());
rep(i,0,n)
{
if(vect[i].second!=0)
{
cout<<sum[i]<<endl;
break;
}
}
}
return 0;
}

Price of a fruit can be zero also. So you will have to make an another array which stores the count of fruits. And then iterate over to get the desired ouput.