CHEFDINE - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: justfun21
Testers: iceknight1093, mexomerf
Editorialist: iceknight1093

DIFFICULTY:

1438

PREREQUISITES:

Sorting

PROBLEM:

A restaurant has N dishes; the i-th of which has category A_i and takes B_i time to be cooked.
Find the minimum possible time needed to get at least K distinct categories of food.

EXPLANATION:

If there are less than K distinct categories the answer is -1.
This can be checked in several different ways, for example:

  • Put all the A_i values into a set and check its size; or
  • Sort the A_i values and count the number of indices such that A_i \leq A_{i+1}.

Now let’s deal with the case when there are \geq K distinct values.

Choosing two different dishes with the same category is clearly not optimal.
This means we choose at most one dish from each category.

For the least total time, from each category we obviously keep only the one that takes the least time to cook.

This can be computed using an array C of length 10^5, initially C_i = \infty for each 1 \leq i \leq 10^5.
Then, for each 1 \leq i \leq N, set C_{A_i} = \min(C_{A_i}, B_i).

Now, C_x contains the minimum time to cook a dish of category x.
The answer is then the sum of the K smallest values of C, which can be found by sorting C.

Instead of an array of size 10^5, you can also use a map (std::map in C++, HashMap/TreeMap in Java, dict in Python) to represent C.

TIME COMPLEXITY:

\mathcal{O}(N\log N) per testcase.

CODE:

Setter's code (C++) 
#include <bits/stdc++.h>
using namespace std;


int main(){
    // setIO("input");
    ios_base::sync_with_stdio(false);
    cin.tie();cout.tie();
    long long TT = 1;
    long long suma = 0;
    cin>>TT;
    for(long long TR = 1;TR <= TT;TR++){
        long long n,k;
        cin>>n>>k;
        suma+=n;
        assert(n>=1 and n<=100000);
        assert(k>=1 and k<=100000);
        vector<long long>a(n),b(n);
        for(long long i=0;i<n;i++){
            cin>>a[i];
            assert(a[i]>=1 and a[i]<=100000);
        }
        for(long long i=0;i<n;i++){
            cin>>b[i];
            assert(b[i]>=0 and b[i]<=100000);
        }
        map<long long,long long>mp;
        for(long long i=0;i<n;i++){
            mp[a[i]] = 10000007;
        }                 
        for(long long i=0;i<n;i++){
            mp[a[i]] = min(mp[a[i]],b[i]);
        }
        vector<long long>time;
        for(auto it:mp){
            if(it.second!=10000007){
                time.push_back(it.second);
            }
        }    
        sort(time.begin(),time.end());
        if(time.size()<k){
            cout<<-1<<"\n";
            continue;
        }
        long long ans = 0;
        for(long long i=0;i<k;i++){
            ans+=time[i];
        }
        cout<<ans<<"\n";
    } 
    assert(suma>=1 and suma<=100000);
    return 0;
}
Tester's code (C++) 
#include <bits/stdc++.h>
using namespace std;
#define int long long
int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int t;
  cin >> t;
  while (t--)
  {
    int n, k;
    cin >> n >> k;
    int a[n], b[n];
    map<int, int> mpp;
    for (int i = 0; i < n; i++){
      cin >> a[i];
    }
    for (int i = 0; i < n; i++){
      cin >> b[i];
    }
    for (int i = 0; i < n; i++){
      if(mpp.find(a[i]) == mpp.end()){
        mpp[a[i]] = b[i];
      }else{
        mpp[a[i]] = min(mpp[a[i]], b[i]);
      }
    }
    vector<int> v;
    for(auto &it: mpp){
      v.push_back(it.second);
    }
    sort(v.begin(), v.end());
    int sum = -1;
    if(v.size() >= k){
      sum = 0;
      for (int i = 0; i < k; i++){
        sum += v[i];
      }
    }
    cout << sum << "\n";
  }
  return 0;
}
Editorialist's code (Python) 
for _ in range(int(input())):
    n, k = map(int, input().split())
    a = list(map(int, input().split()))
    b = list(map(int, input().split()))
    least = [10**12 for i in range(10**5 + 5)]
    for i in range(n): least[a[i]] = min(least[a[i]], b[i])
    ans = sum(sorted(least)[0:k])
    print(ans if ans < 10**12 else -1)
2 
#include <bits/stdc++.h>
using namespace std;

int main() {
	// your code goes here
	int t;
	cin>>t;
	while(t--)
	{
	    int n,k, ans=0;
	    bool notp=false;
	    cin>>n>>k;
	    int a[n], b[n];
	    unordered_map<int,int> mp;
	    priority_queue<int, vector<int>> pq;
	    
	    for(int i=0; i<n; i++)
	    {
	        if(mp.find(a[i])!=mp.end())
	        {
	            if (b[i]<mp[a[i]]) mp[a[i]]=b[i];
	        }
	        else mp[a[i]]=b[i];
	    }
	    if(mp.size()<k) notp=true;
	    for(auto itr=mp.begin(); itr!=mp.end(); itr++)
	    {
	        pq.push(itr->second);
	        if(pq.size()>k) pq.pop();
	    }
	    while(!pq.empty())
	    {
	        ans+=pq.top();
	        pq.pop();
	    }
	    if(notp==true) cout<<-1<<endl;
	    else cout<<ans<<endl;
	}
	return 0;
}

This code also follows the same logic but the last test case is showing WA. What can be wrong with the code?

3

In the last case, the answer is not bounded under an integer the answer may be long long int.

2 Likes
4

Thanks, My code works after this correction.

5

Pls help me in finding error as it gives correct ans on running with sample cases but on submitting it does not passes all cases.

include
#include<bits/stdc++.h>

using namespace std;
void solution(){
int t;cin>>t;while(t–){
int n,k; cin>>n>>k;
vectora(n) ;
vectorb(n);
setSet;
setSetb;
for(int i =0;i<n; i++){
cin>>a[i];
}
for(int i =0;i<n; i++){
cin>>b[i];
}
sort(b.begin(),b.end());
for(int j =0; j<n; j++){
Set.insert(a[j]);
}
for(int j =0; j<n; j++){
Setb.insert(b[j]);
}
int s = Set.size();
set::iterator itr;
int ct=0;

    int long long sum =0; 
    if(k>s)cout<<"-1"<<endl;
    else{
        for(itr = Setb.begin(); itr != Setb.end(); itr++){
        if(ct<k)
        {
            sum += (*itr);
        }
        ct++;
    }
        cout<<sum<<endl;
    }
}

}

int main() {

// your code goes here
solution();
return 0;

}