SPCAP - Editorial

Practice
Contest Source
Author, Tester and Editorialist : Rohail Alam

DIFFICULTY:

Easy

PREREQUISITES:

Implementation

PROBLEM:

Given N values, find out if it is possible to achieve a desired condition subject to some constraints.

EXPLANATION:

The minimum number of capsules one can be left with will be the count of capsules with the maximum occurring capsule size, and of course - the maximum number of capsules will just be N (in this case we don’t put any of the capsules into each other).

If we take the capsules with size occurring most number of times, you can observe that all capsules smaller in size can be put into each other in ascending order of size, which in turn an be placed in the boxes of larger size in the same order.

To further elaborate, we can refer to this example - 3 6 4 2 4 1 7
Re-arranging the sizes in ascending order - 1 2 3 4 4 6 7

Notice that the capsule of size 4 is the most occurring capsule.
We first put the capsules of smaller size than 4 into each other:

  • Capsule 1 is placed in Capsule 2
  • Capsule 2 is placed in Capsule 3
  • Capsule 3 is placed in Capsule 4 ( can be placed in Capsule 5 too)

The resulting array of capsules left will be - 4 4 6 7

Now, we can place the capsule of size 4 into the capsules of larger size in an ascending order (this is possible as there is no other value in the array with frequency \gt 2)

  • Capsule 4 (of size 4) is placed in Capsule 6
  • Capsule 6 is placed in Capsule 7

The final array of sizes we obtain is - 4 7, whose length is the same as the frequency of capsules of size 4 (which is 2) and is the least possible size this array can have. Assuming that this value is M :

  • The answer will be “Yes” if M \leq K \leq N
  • “No” otherwise

TIME COMPLEXITY:

O(n . log(n))

SOLUTION:

C++ Solution
#include<bits/stdc++.h>
using namespace std;

int main(){
    int tt;
    cin>>tt;
    while(tt--){
        int n,k;
        cin>>n>>k;
        vector<int> x(n);
        map<int,int> mpp;
        for(int i = 0;i<n;++i){
            cin>>x[i];
            mpp[x[i]]++;
        }
        int ans = 0;
        for(auto x:mpp){
            ans = max(ans,x.second);
        }
        if(ans <= k && k <= n){
            cout<<"YES\n";
        }
        else cout<<"NO\n";
    }
}